Codeforces Round #395 (Div. 2) C. Timofey and a tree
2023-04-18 12:34:18 时间
终于难得的打了场早的cf 然后华丽丽地跪了....... AB题一下水过,然后一直在尝试读懂C题的题意...好不容易完全明白后赶紧写了发结果递归函数一个参数码歪了debug了好久,很巧地在我刚准备交时比赛正好结束..=_=...等系统终测完整个比赛后,贴上去交...AC了.....心塞塞[捂脸]....
题意:给你一颗有n个节点的树,让你选一个节点作为根(根的颜色可以无视),使得这个根上的所有子树都是同一种颜色,如:。
思路:这里说下我自己的方法。我是dfs加剪枝(感觉很奇葩的剪枝方式,,,我自己还没能完全证明为什么要这么贪心,等想明白后回来补=_=)。
首先是任选一个节点,将它作为根然后dfs它的每棵子树,判断每株子树是否为同色;如果有一株以上的子树不是全同色,像这样的,答案肯定就是"NO"了;如果是0株,那这个点就可以作为根了。
若只有一株,像下面这幅:
。 一开始以节点1作为根判断的时候,判断到有一株的子树并不是全部同色的,并且用个全局变量记录这个不同色节点(即4号节点)的父节点(即3号节点)。然后以这个记录的结点(3号节点)作为根,进行跟上述相同的操作。 另外,还要有个标记数组,用于标记那些已经作为过根判断的节点,如果有发现当前要判断为根的点之前已经判断过了,则可直接输出答案"NO"了。
1 /** 2 * @author Wixson 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 #include <algorithm> 9 #include <queue> 10 #include <stack> 11 #include <vector> 12 #include <utility> 13 #include <map> 14 #include <set> 15 const int inf=0x3f3f3f3f; 16 const double PI=acos(-1.0); 17 const double EPS=1e-8; 18 using namespace std; 19 typedef long long ll; 20 typedef pair<int,int> P; 21 22 int n; 23 int u,v; 24 vector<int> G[200050]; 25 int c[200050]; 26 int book[200050]; 27 int ans; //记录答案节点 28 int wa; //记录子树中不同色节点的父节点 29 // 30 int bfs(int r,int father,int color) 31 { 32 // 33 for(int i=0;i<G[r].size();i++) 34 { 35 if(G[r][i]!=father) 36 { 37 if(c[G[r][i]]==color) 38 { 39 if(bfs(G[r][i],r,color)==-1) return -1; 40 } 41 else 42 { 43 wa=r; 44 return -1; 45 } 46 } 47 } 48 return 0; 49 } 50 // 判断节点r能否作为根 51 void judge(int r) 52 { 53 book[r]=1; 54 int cnt_wa=0; 55 for(int i=0;i<G[r].size();i++) 56 { //判断每株子树是否为同色 57 if(bfs(G[r][i],r,c[G[r][i]])==-1) 58 { 59 cnt_wa++; 60 } 61 } 62 // 63 if(cnt_wa==0) 64 { 65 ans=r; 66 return; 67 } 68 else if(cnt_wa>1||book[wa]) //如果不同色子树超过一株或节点wa曾判断过 69 { 70 ans=0; 71 return; 72 } 73 else 74 { 75 judge(wa); 76 } 77 } 78 // 79 int main() 80 { 81 //freopen("input.txt","r",stdin); 82 scanf("%d",&n); 83 for(int i=0;i<n-1;i++) 84 { 85 scanf("%d%d",&u,&v); 86 G[u].push_back(v); 87 G[v].push_back(u); 88 } 89 for(int i=1;i<=n;i++) scanf("%d",&c[i]); 90 // 91 judge(1); 92 // 93 if(ans) printf("YES %d ",ans); 94 else printf("NO "); 95 return 0; 96 }
相关文章
- 80%Nature读者都在用ChatGPT,科研方向最多的竟是头脑风暴!
- 六年秘密武器测试,ChatGPT必应暴打谷歌幕后大棋曝光!
- 解读 ChatGPT 背后的研究力量:90 后成主力军,大厂不再是顶尖 AI 人才第一选择
- 美团无人机获中国民航局试运行审定,系统可调度600公里内无人机
- 手机端ChatGPT搜索来了!微软2周火速上线,@Bing即用
- 马库斯:新必应比ChatGPT更狂野,微软是故意的还是不小心?
- ChatGPT之后何去何从?LeCun新作:全面综述下一代「增强语言模型」
- ChatGPT火爆,最全prompt工程指南登GitHub热榜,标星4.7k!
- 颠覆传统图文?ChatGPT写书放网上卖,人类作者:该管管了
- 关于ChatGPT八个技术问题的猜想
- 跑ChatGPT体量模型,从此只需一块GPU:加速百倍的方法来了
- AI自给自足!用合成数据做训练,效果比真实数据还好
- ChatGPT上岗医疗还有多远?哈佛教授亲测表现接近医生,云知声被曝打造行业版
- 谷歌摸着ChatGPT过河:没了热度,传统搜索引擎还是吊打LLM
- 复旦发布中国版ChatGPT:MOSS开启测试冲上热搜,服务器挤爆
- 打造中国版 ChatGPT,国内有哪些学术力量能抢滩?
- ChatGPT成功背后的技术原因及其对生命科学领域的启发
- 跟李沐学ChatGPT背后技术:67分钟读透InstructGPT论文
- 微软消灭了ChatGPT的感情,必应更新引发粉丝强烈不满:是时候再见了
- 雷军计划将铁蛋、铁大推向海外;全球首本ChatGPT撰写的图书即将出版;给员工打“低绩效”,Meta新一轮裁员将至 | T资讯