关于3.13百度后端开发笔试第三题。。

当时根本不会做，后来发现是用树形dp但是我不会（哭），这几天一直在学，终于按自己的方法写了一遍，但是没有题目测试了，请大伙帮忙看看对不对，我加了点输出，自己测试了几个是对的。顺带一提，第二题我过了92%怀疑是int整形(n-1)*n/2溢出的原因，有没有小伙伴和我一样的，讨论一下。

RRBRBRR

1 2

1 3

2 4

4 5

5 6

5 7

输出：14

BBBRB

1 2

3 1

2 4

5 2

输出：3

import java.util.*;

public class Main {

    static int[] dp;//d[i]表示以i为根节点的树的连通块个数
    static String color ;//第i个结点的颜色为s.charAt(i-1)
    static int[][] mege;//记录操作的数组
    static Set[] s;//s[i]表示第i个结点的子节点集合
    static int[] f ;//第i个节点的父亲
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//结点的数量
        String st = sc.nextLine();//去除空格
        color = sc.nextLine();//颜色
        dp = new int[n+1];
        mege = new int[n-1][2];//共有n-1条边
        s = new Set[n+1];//第i个结点的子集
        f = new int[n+1];//第i个节点的父亲结点
        for(int i=0;i<n-1;i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            //让小的结点作为父结点,大的是子节点
            int father = Math.min(a,b);
            int son = Math.max(a,b);
            mege[i][0]=father;
            mege[i][1] = son;//记录每一次的操作
            if(s[father]==null)
                s[father] = new HashSet();
            s[father].add(son);//儿子加入集合
            f[son] = father;

        }
        int root = 1;//设1为父亲结点
        dfs(root);
 //       for(int i=1;i<dp.length;i++)
 //           System.out.println("第"+i+"个节点的连通块个数为："+dp[i]);
        int sum = 0;//记录答案
        //处理操作的数组
        for(int i=0;i<mege.length;i++)
        {
            //对每一个操作数组mege[0]到mege[1]的边被切断了
            int a = mege[i][0];
            int b = mege[i][1];
            int father = Math.min(a,b);//较小的是父结点
            int son = Math.max(a,b);//较大的是儿子
            int temp=0;
            if(color.charAt(father-1)==color.charAt(son-1))//如果父子的颜色相同
                temp = Math.abs(dp[son]-(dp[1]-dp[son]+1));//儿子的连通块不变，根节点的连通块要减去儿子的再+1
            else //如果父子的颜色相同
                temp = Math.abs(dp[son]-(dp[1]-dp[son]));//儿子连通块不变，根节点的减去儿子即可
            sum+=temp;
            //System.out.println("删除"+father+"和"+son+"之间的边的权值为："+temp);
        }
        System.out.println(sum);
    }
    static void dfs(int x){//表示第x个节点的同色连通块数量
        dp[x] = 1;//本身是1
        if(s[x]==null)//如果是叶子结点
            return;
        Iterator<Integer> iterator = s[x].iterator();
        while(iterator.hasNext())
        {
            int a = iterator.next();//a为x的子节点
            dfs(a);//先搞定子节点
            if(color.charAt(x-1)==color.charAt(a-1))//如果父子结点的颜色相同
                dp[x]+=dp[a]-1;//要减去1
            else
                dp[x]+=dp[a];//颜色不同直接加上子节点的连通块个数
        }
    }
}

#我的实习求职记录#