首页 > 代码库 > 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