首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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
全部评论
推荐
最新
楼层
蔚来
校招火热招聘中
官网直投
相关推荐
ikun642
06-08 12:37
西南交通大学 统计学类
简历求拷打
大二在读,想暑假找份数据分析的日常实习,麻烦大家帮忙看看简历
简历被挂麻了,求建议
简历中的项目经历要怎么写
点赞
评论
收藏
分享
秋招求职助手
06-04 11:11
中国农业大学 生物科学类
不要焦虑,实习机会还有很多
基本日更10几家,实习机会还是有的,拒绝焦虑
点赞
评论
收藏
分享
hey_hey
05-11 22:26
已编辑
算法工程师
go后端,求大佬指点,找实习被拒麻了😭😭😭
点赞
评论
收藏
分享
小lin在找工作
06-04 18:54
广州商学院 外国语言文学类
这样的我,请问能找到实习工作吗
点赞
评论
收藏
分享
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
24届985计算机废物春招感想(央国企、银行)
1.8W
2
...
问一下大家的实习薪资是多少?
8818
3
...
有个好导师真幸福
5445
4
...
美团 实习
5106
5
...
颇有感慨
4474
6
...
导师不放实习,实习偷跑一个月经历
3817
7
...
【💰有奖征集】软件开发笔面经邀你来分享!🙋♂️
3217
8
...
许愿今天收到华子offer
3133
9
...
华为 泡死了
2560
10
...
当我终于爬上山峰,眼前却是迷路丛生
2355
正在热议
#
和牛牛一起刷题打卡
#
32280次浏览
2287人参与
#
你的简历改到第几版了
#
341366次浏览
5121人参与
#
不去互联网可以去金融科技
#
38424次浏览
435人参与
#
牛客帮帮团来啦!有问必答
#
1238589次浏览
17862人参与
#
你的秋招进展怎么样了
#
579263次浏览
14128人参与
#
你觉得今年秋招难吗
#
340040次浏览
6064人参与
#
OPPO开奖
#
43157次浏览
601人参与
#
数据人的面试交流地
#
214690次浏览
4405人参与
#
软件开发笔面经
#
13181次浏览
362人参与
#
参加过提前批的机械人,你们还参加秋招么
#
15176次浏览
361人参与
#
硬件打工人的必备素养
#
5552次浏览
56人参与
#
你最多能接受一周加班几个小时
#
4749次浏览
51人参与
#
我在牛爱网找对象
#
62019次浏览
489人参与
#
你觉得通信/硬件有必要实习吗?
#
28209次浏览
469人参与
#
春招别灰心,我们一人来一句鼓励
#
31296次浏览
452人参与
#
公司情报交流地
#
13787次浏览
83人参与
#
你的秋招进行到哪一步了
#
413732次浏览
6845人参与
#
现在还是0offer,延毕还是备考
#
421990次浏览
4926人参与
#
24届软开秋招面试经验大赏
#
1204599次浏览
18386人参与
#
听劝,我这个简历该怎么改?
#
65282次浏览
659人参与
#
0offer是寒冬太冷还是我太菜
#
464810次浏览
5183人参与
#
职场上哪些事情令人讨厌
#
3346次浏览
25人参与
牛客网
牛客企业服务