2023-03-30 17:44 已编辑 北京科技大学 Java
关注
3.28百度笔试b卷第3题
今天回想起来突然思路打开了，当局者迷啊，题目、思路和代码如下，请各位大佬看看有没有问题。
原题：
给出一棵树，每个结点用红色或蓝色染色。定义一条边的贡献为删掉该条边得到的两个子树的同色联通块数的差的绝对值，一棵树的贡献为树上每条边的贡献之和，求该树的贡献。
样例输入：
4
RRBB
1 2
2 3
1 4
样例输出：
2
样例解释：
删除1-2这条边，两个子树的同色联通块都为2，差的绝对值为0
删除2-3这条边，两个子树的同色联通块分别为1,2，差的绝对值为1
删除1-4这条边，两个子树的同色联通块分别为2,1，差的绝对值为1
故答案为0+1+1=2。
颜色连通块我没理解错的话应该是，不管多少个节点，只要连通且颜色相同就算一个连通块。示例有点不充分让人混淆，比如三个连通的颜色相同的节点a-b-c，是算两个连通块a-b和b-c还是算一个整体呢，我认为是一个整体。
思路和代码见图
原题：
给出一棵树，每个结点用红色或蓝色染色。定义一条边的贡献为删掉该条边得到的两个子树的同色联通块数的差的绝对值，一棵树的贡献为树上每条边的贡献之和，求该树的贡献。
样例输入：
4
RRBB
1 2
2 3
1 4
样例输出：
2
样例解释：
删除1-2这条边，两个子树的同色联通块都为2，差的绝对值为0
删除2-3这条边，两个子树的同色联通块分别为1,2，差的绝对值为1
删除1-4这条边，两个子树的同色联通块分别为2,1，差的绝对值为1
故答案为0+1+1=2。
颜色连通块我没理解错的话应该是，不管多少个节点，只要连通且颜色相同就算一个连通块。示例有点不充分让人混淆，比如三个连通的颜色相同的节点a-b-c，是算两个连通块a-b和b-c还是算一个整体呢，我认为是一个整体。
思路和代码见图
全部评论
年龄太大只能去送外卖
中国人民大学 Java
我当时想的是从下往上的层序遍历，还没来的及写完，不过也无所谓了，感觉百度并不想招我
想去东北泡澡的共享单车人求你们别卷了
Queen Mary University of London 机器学习
问问这是啥软件分享出来的图啊，好看！
不要再熬夜了
美团_到家医药_后端开发
感谢佬分享代码，写的很清晰，有学到东西😋
相关推荐
点赞 评论 收藏
分享
06-12 11:54
中山大学 C++ 点赞 评论 收藏
分享
程序员牛肉：但凡是个大公司，他就会有面试评价。
所以你说的这个脏不脏面评的这个就纯属扯淡。你要是面试的时候答成一坨了，那肯定会脏面评。而且尤其是算法，你如果说算法没准备好的话，那你就千万不要你自己，你如果算法一旦做不出来，并且前面答的不是特别好的话，那你近四五个月就别想面字节了。 点赞 评论 收藏
分享