ac

整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。
这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：
1.如果某个员工来了，那么这个员工的所有直接下级都不能来。
2.派对的整体快乐值是所有到场员工快乐值的累加。
3.你的目标是让派对的整体快乐值尽量大。
给定一棵多叉树，请输出派对的最大快乐值。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.*;


class Employee {
    int val;
    public int happy; //这名员工带来的快乐值
    List<Employee> subordinates; //这名员工有哪些直属下级

    public Employee(int val, int happy, List<Employee> subordinates) {
        this.val = val;
        this.happy = happy;
        this.subordinates = subordinates;
    }
    public Employee(int val, int happy) {
        this.val = val;
        this.happy = happy;
        this.subordinates = new ArrayList<>();
    }
}

// 是否有使用根的最大happiness
class Return{
    int withRoot;
    int withOutRoot;

    public Return(int withRoot, int withOutRoot) {
        this.withRoot = withRoot;
        this.withOutRoot = withOutRoot;
    }
}

public class Main{
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int mod=(int)Math.pow(10,9)+7;

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int rootVal = sc.nextInt();
        int[] happy = new int[n+1];
        for(int i=1;i<=n;i++){
            happy[i] = sc.nextInt();
        }
        Map<Integer, Employee> mp = new HashMap<>(n);
        for (int i = 0; i < n-1; i++) {
            int u1 = sc.nextInt();
            int u2 = sc.nextInt();
            if(!mp.containsKey(u1)){
                Employee employee = new Employee(u1, happy[u1]);
                mp.put(u1, employee);
            }
            if(!mp.containsKey(u2)){
                Employee employee = new Employee(u2, happy[u2]);
                mp.put(u2, employee);
            }
            Employee u1Employee = mp.get(u1);
            u1Employee.subordinates.add(mp.get(u2));
        }
        Employee root = mp.get(rootVal);
        Return ans = getMaxHappy(root);
        System.out.println(Math.max(ans.withOutRoot, ans.withRoot));
    }

    // https://www.cnblogs.com/coding-gaga/p/11080111.html
    static Return getMaxHappy(Employee root){
        if(root == null){
            return new Return(0,0);
        }
        if(root.subordinates == null || root.subordinates.size() == 0){
            return new Return(root.happy, 0);
        }
        int sumValWithOutRoot = 0; // 不包括当前root
        int sumValWithRoot = root.happy; // 包括当前root
        for(Employee employeeChild: root.subordinates){
            Return happySon = getMaxHappy(employeeChild);

            sumValWithRoot += happySon.withOutRoot;// 包括当前root, 则不能包含直接子节点

            sumValWithOutRoot += Math.max(happySon.withRoot, happySon.withOutRoot);
        }
        return new Return(sumValWithRoot, sumValWithOutRoot);
    }

}
/*
3 1
5 1 1
1 2
1 3

5

48 11
825 815 5 996 172 528 309 185 309 473 408 34 776 498 952 866 674 881 135 102 50 408 609 167 514 171 750 880 227 186 338 246 264 294 18 372 932 14 653 987 843 868 585 506 123 399 916 759
11 9
9 27
9 40
9 37
40 36
11 16
11 13
16 48
16 46
40 4
37 5
36 7
9 15
36 42
37 19
48 35
9 28
19 45
13 10
40 2
16 12
9 41
36 31
45 3
5 6
31 22
6 33
45 8
5 30
9 23
9 43
48 14
6 29
9 25
8 34
19 1
29 26
42 32
33 18
11 47
29 44
36 38
33 24
15 39
36 20
27 17
13 21

16332
 */