首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
今晚不熬夜_
广东工业大学 电子信息类
发布于广东
关注
已关注
取消关注
@年轻的靓仔在吐槽:
百度笔试第三题
小红拿到了一棵树,每个节点被染成了红色或者蓝色。小红定义每条边的权值为:删除这条边时,形成的两个子树的同色连通块数量之差的绝对值。小红想知道,所有边的权值之和是多少?输入描述第一行输入一个正整数 n ,代表节点的数量。第二哈输入一个长度为 n 且仅由 R 和 B 两种字符组成的字符串。第 i 个字符为 R 代表 i 号节点被染成红色,为 B 则被染成蓝色。接下来的 n−1 行,每行输入两个正整数 u 和 v ,代表节点 u 和节点 v 有一条边相连。1≤n≤200000int main() { int n; cin >> n; vector<bool> colors_bl(n + 1, false); vector<unordered_set<int>> edges(n + 1, unordered_set<int>()); for (int i = 1; i < n + 1; ++i) { char ch; cin >> ch; if (ch == 'B') { colors_bl[i] = true; } } for (int i = 0; i < n - 1; ++i) { int e1, e2; cin >> e1 >> e2; edges[e1].insert(e2); edges[e2].insert(e1); } vector<bool> is_seen(n+1, false); vector<int> dp(n+1, 0); // dfs返回结果是该节点作为根节点所包含的联通数量 function<int(int, vector<bool>&)> dfs = [&](int i, vector<bool>& is_seen) { int tmp = 0; int sum = 0; vector<int> tmp_v; for (auto&& v : edges[i]) { if (is_seen[v]==false) { tmp++; is_seen[v] = true; int nums = dfs(v, is_seen); sum += nums; tmp_v.push_back(v); } } dp[i] = sum; if (tmp == 0) { dp[i] = 1; return 1; } else { if (tmp == 1) { if (colors_bl[i] != colors_bl[tmp_v[0]]) { dp[i] += 1; } } else { if (colors_bl[i] == colors_bl[tmp_v[0]] && colors_bl[i] == colors_bl[tmp_v[1]]) { dp[i] -= 1; } else if (colors_bl[i] != colors_bl[tmp_v[0]] && colors_bl[i] != colors_bl[tmp_v[1]]) { dp[i] += 1; } } } return dp[i]; }; is_seen[1] = true; auto res = dfs(1, is_seen); // cout << endl; unordered_set<int> ss; int sum = 0; for (int i = 1; i <= n; ++i) { for (auto&& it : edges[i]) { int a1 = min(dp[i], dp[it]); int a2 = abs(res - a1); if (colors_bl[i] == colors_bl[it]) { a2++; } sum += abs(a2 - a1); } } cout << sum/2 << endl;}#include "header.h"int main() { int n; cin >> n; vector<bool> colors_bl(n + 1, false); vector<unordered_set<int>> edges(n + 1, unordered_set<int>()); for (int i = 1; i < n + 1; ++i) { char ch; cin >> ch; if (ch == 'B') { colors_bl[i] = true; } } for (int i = 0; i < n - 1; ++i) { int e1, e2; cin >> e1 >> e2; edges[e1].insert(e2); edges[e2].insert(e1); } vector<bool> is_seen(n+1, false); vector<int> dp(n+1, 0); // dfs返回结果是该节点作为根节点所包含的联通数量 function<int(int, vector<bool>&)> dfs = [&](int i, vector<bool>& is_seen) { int tmp = 0; int sum = 0; vector<int> tmp_v; for (auto&& v : edges[i]) { if (is_seen[v]==false) { tmp++; is_seen[v] = true; int nums = dfs(v, is_seen); sum += nums; tmp_v.push_back(v); } } dp[i] = sum; if (tmp == 0) { dp[i] = 1; return 1; } else { if (tmp == 1) { if (colors_bl[i] != colors_bl[tmp_v[0]]) { dp[i] += 1; } } else { if (colors_bl[i] == colors_bl[tmp_v[0]] && colors_bl[i] == colors_bl[tmp_v[1]]) { dp[i] -= 1; } else if (colors_bl[i] != colors_bl[tmp_v[0]] && colors_bl[i] != colors_bl[tmp_v[1]]) { dp[i] += 1; } } } return dp[i]; }; is_seen[1] = true; auto res = dfs(1, is_seen); // cout << endl; unordered_set<int> ss; int sum = 0; for (int i = 1; i <= n; ++i) { for (auto&& it : edges[i]) { int a1 = min(dp[i], dp[it]); int a2 = abs(res - a1); if (colors_bl[i] == colors_bl[it]) { a2++; } sum += abs(a2 - a1); } } cout << sum/2 << endl;}
点赞 7
评论 3
全部评论
推荐
最新
楼层
秋招专场
校招火热招聘中
官网直投
相关推荐
kk_h
06-01 01:42
西安华西专修大学 计算机类
offer选择
大佬们可以帮忙选择一下offer吗1联通软件研究院广州:21-23w,不确定能不能拿满,看绩效给钱,abcd绩效网上风评不好,固定有人背低绩效,工作强度看项目,校招生国企稳定;2人保财险湖北:15w左右,要先下基层市级公司一到两年(有可能在武汉市级公司),工资基本前三年是死的,保险后台可能也会技术衰退,三年后要是没法升职可能就一直死工资了,不过好像不怎么加班比较轻松;3广州银行:20-21w,网上风评不好,说是可能拿不到这个数,内部晋升路线也不明确三家都是科技岗位,1和3网上风评都不是很好,2网上基本上没有消息(好消息和坏消息都无)
投递人保科技等公司9个岗位 >
点赞
评论
收藏
转发
Nanomoa
05-30 22:55
青岛科技大学 计算机类
golang 简历求拷打,虚心请教
学校普通一本,第一次写简历,求佬们给点建议😭
点赞
评论
收藏
转发
最喜欢夏天的花生米很想去夏威夷
昨天 16:21
山东建筑大学 计算机类
?Java已经到这种地步了吗
点赞
评论
收藏
转发
土豆小魔王
04-27 01:29
已编辑
香港大学 计算机类
记录一下失败的找实习记录
累了华为:一面挂,面试官问我GPA和排名,我说不出来😭小米 sre工程师/cpp客户端:简历挂特斯拉 cpp客户端:简历挂4399 游戏客户端开发:笔试挂腾讯 pcg桌面cpp开发:一面挂普联:没消息百度:学姐给内推,好像没hc了直接发的拒信快手 cpp:简历挂oppo:一面被华为顶掉了,挂中行:没消息交行:没消息完美世界 游戏策划/客户端:没消息联想 python开发 没消息比亚迪 没消息埃森哲 没消息
投递4399游戏等公司10个岗位
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
OPPO OC,欧欧欧欧欧欧
6514
2
...
拒了荣耀offer,感觉自己很丑陋
3761
3
...
【🎁】25届硬件牛牛互助计划(1期)
3583
4
...
哈啰Java实习一面40min
3406
5
...
计算机专业可以去哪些央国企(总论篇)?
3345
6
...
给你们预测一下今年的秋招!
3018
7
...
《工贼》
2944
8
...
【获奖公示】V你50📍(夏季刷题打卡第一周参与奖)
2901
9
...
海康威视暑期实习-智能硬件
2731
10
...
深圳蟑螂真的很可怕吗
2385
正在热议
#
牛客帮帮团来啦!有问必答
#
1113809次浏览
16759人参与
#
简历无回复,你会继续海投还是优化再投?
#
24101次浏览
345人参与
#
OPPO开奖
#
6625次浏览
161人参与
#
和牛牛一起刷题打卡
#
16054次浏览
1476人参与
#
通信硬件薪资爆料
#
260607次浏览
2445人参与
#
互联网公司评价
#
95803次浏览
1247人参与
#
不去互联网可以去金融科技
#
9345次浏览
125人参与
#
通信和硬件还有转码的必要吗
#
10169次浏览
98人参与
#
提前批和秋招有什么区别
#
29877次浏览
720人参与
#
面试被问第一学历差时该怎么回答
#
19003次浏览
211人参与
#
你收到了团子的OC了吗
#
534268次浏览
6347人参与
#
现在还是0offer,延毕还是备考
#
411391次浏览
4876人参与
#
应届生初入职场,求建议
#
35577次浏览
814人参与
#
如何看待offer收割机的行为
#
248498次浏览
3481人参与
#
实习生应该准时下班吗
#
95127次浏览
714人参与
#
参加过提前批的机械人,你们还参加秋招么
#
14272次浏览
349人参与
#
晒一晒我的offer
#
3794500次浏览
58264人参与
#
工作两年想退休了
#
20045次浏览
261人参与
#
你们的毕业论文什么进度了
#
603377次浏览
6767人参与
#
你的秋招进行到哪一步了
#
399227次浏览
6718人参与
#
本周投递记录
#
222651次浏览
5412人参与
#
你的秋招进展怎么样了
#
560947次浏览
13982人参与
牛客网
牛客企业服务