生命之树题解(2015-Java-B-10)

题目描述

在X森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得 S 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。

算法分析

树状dp，无根树转有根树，思维难度较大，此处运用dfs搜索

状态表示

在以root为根的子树中包含u的所有连通块的权值的最大值

状态计算

从根结点开始深度优先遍历每个子结点如果子结点权值为负则舍弃

参考文献

蓝桥杯郑未老师的视频讲解

Java 代码

import java.util.*;

public class Main {
    private static int n;
    private static long res;
    private static long[] w;
    private static List<Integer>[] g;
    private static long[] f ;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n =sc.nextInt();
        w = new long[n+1];
        g = new ArrayList[n+1];
        f = new long[n+1];

        for(int i = 0;i < n+1; i++){
            g[i] = new ArrayList<Integer>();
        }

        for(int i = 1;i <= n;i ++){
             w[i] = sc.nextLong();
        }

        for(int i = 0;i < n - 1;i ++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g[a].add(b);
            g[b].add(a);
        }

        dfs(1,0);
        res = f[1];
        for(int i = 2; i < n+1; i++){
            if(res<f[i]){
                res = f[i]; 
            }
        }
        System.out.println(res);
    }
    /**
    *root作为根所代表的子树有一个最大权和，将其存储在f[root]中
    */
    private static void dfs(int root,int father){
        f[root] = w[root];
        for(int i = 0; i < g[root].size(); i++){
            Integer child = g[root].get(i);
            if(child == father){
                continue;
            }
            dfs(child,root);
            if(f[child] > 0){
                f[root] += f[child];
            }
        }
    }    
}