舞会和打家劫舍III一样，本质是相邻两个节点不能选，代码如下

打家劫舍III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

 3
/ \

2 3
\ \
3 1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

3
/ \
4 5
/ \ \
1 3 1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

java代码

class Solution {
    public int rob(TreeNode root) {
        if( root == null )return 0;
        int[] res = max( root );
        return Math.max( res[0], res[1]);
    }
    public int[] max(TreeNode root){
        int[] res = new int[2];
        if( root == null )return res;
        int[] left = max( root.left );
        int[] right = max( root.right );
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0],right[1]);//不选根节点
        res[1] = root.val + left[0] + right[0];//选根节点
        return res;
    }
}

没有上司的舞会

java 代码

//假设幸福值一样并且每个上司最多俩员工的话，这道题就变成树状问题的打家劫舍
//此题幸福值不同且是多叉树，问题的难度就增加了，增加到了多叉树的遍历上。本质上还是打家劫舍问题
//需要建图，然后深度遍历累加值即可

import java.io.*;
import java.lang.*;
import java.util.*;

class Main{
    static int n = 0, N = 6010;
    static int[] Happy = new int[N];//幸福值
    static int[] h = new int[N];//邻接表
    static int[] e = new int[N], ne = new int[N];//图的单链表
    static int idx = 1;
    static int[][] f = new int[N][2];//状态数组
    static boolean[] st = new boolean[N];
    static void add(int a, int b){//建表
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++;  
    }
    static void dfs(int u){
        f[u][1] = Happy[u];
        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            dfs(j);
            f[u][0] += Math.max(f[j][0], f[j][1]);
            f[u][1] += f[j][0];
        }
    }

    public static void main(String[] args)throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(buf.readLine());
        for(int i = 1; i <= n; ++i){//存储幸福值
            Happy[i] = Integer.valueOf(buf.readLine());
        }
        Arrays.fill(h, -1);
        int m = n - 1;
        while( m -- != 0 ) {
            String[] info = buf.readLine().split(" ");
            int a = Integer.valueOf(info[0]);
            int b = Integer.valueOf(info[1]);
            add(b, a);//因为b是上司因此需要把a连接到b的后面
            st[a] = true;//表示当前节点有父节点
        }
        //计算得到根节点
        int u = 1;
        while(st[u]){
            u++;
        }
        dfs(u);
        System.out.print(Math.max(f[u][0], f[u][1]));
    }
}