首页 > 代码库 > UVA - 725
UVA - 725
https://odzkskevi.qnssl.com/8b9d8bb43198f28efe782047d56ab361?v=1501987995
1 /* 2 题目大意:一个树上有n个节点,n-1条边,每个节点上有一个颜色 3 现要求选取其中一个节点为根,要求子树的颜色相同,问是否能够达到要求。 4 题目分析:两个有共同边的节点,如果颜色不一样,那么肯定会有其中一个点选为根 5 记录这个点的度+1,总的counts+1,最后遍历数组,找出度和counts的大小相同的点并输出 6 如果没有即是不能达到要求。 7 */ 8 #include <cstdio> 9 #include <cstring> 10 using namespace std; 11 int const maxn = 100005; 12 struct node{ 13 int u,v; 14 }a[maxn]; 15 int c[maxn]; 16 int degree[maxn]; 17 int main(){ 18 int n; 19 scanf("%d",&n); 20 for(int i=1;i<n;i++) 21 scanf("%d%d",&a[i].u ,&a[i].v ); 22 for(int i=1;i<=n;i++) scanf("%d",&c[i]); 23 int counts=0; 24 memset(degree,0,sizeof(degree)); 25 for(int i=1;i<n;i++){ 26 if(c[a[i].u]!=c[a[i].v]){ 27 counts++; 28 degree[a[i].u ]++; 29 degree[a[i].v ]++; 30 } 31 } 32 for(int i=1;i<=n;i++){ 33 if(counts==degree[i]){ 34 printf("YES\n%d\n",i); 35 return 0; 36 } 37 } 38 printf("NO\n"); 39 return 0; 40 } 41 /////Runtime error on test 42 #include <iostream> 43 #include <stdio.h> 44 #include <string.h> 45 using namespace std; 46 const int maxn=100005; 47 struct node { 48 int u,v; 49 }a[maxn]; 50 int c[maxn],degree[maxn]; 51 int main(){ 52 int n; 53 scanf("%d",&n); 54 for(int i=1;i<n;i++) 55 scanf("%d%d",&a[i].u,&a[i].v); 56 for(int i=1;i<=n;i++) 57 scanf("%d",&c[i]); 58 int ans=0; 59 memset(degree,0,sizeof(degree)); 60 for(int i=1;i<n;i++){ 61 if(c[a[i].u]!=c[a[i].v]){ 62 ans++; 63 degree[a[i].u]++; 64 degree[a[i].v]++; 65 } 66 } 67 for(int i=1;i<=n;i++){ 68 if(ans==degree[i]){ 69 printf("YES\n%d\n",i); 70 return 0; 71 } 72 } 73 printf("NO\n"); 74 return 0; 75 }
UVA - 725
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。