/*
题目大意:一个树上有n个节点,n-1条边,每个节点上有一个颜色
现要求选取其中一个节点为根,要求子树的颜色相同,问是否能够达到要求。
题目分析:两个有共同边的节点,如果颜色不一样,那么肯定会有其中一个点选为根
记录这个点的度+1,总的counts+1,最后遍历数组,找出度和counts的大小相同的点并输出
如果没有即是不能达到要求。
*/
#include < cstdio > #include < cstring > using namespace std;
int const maxn = 100005;
struct node {
int u,
v;
}
a[maxn];
int c[maxn];
int degree[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) scanf("%d%d", &a[i].u, &a[i].v);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
int counts = 0;
memset(degree, 0, sizeof(degree));
for (int i = 1; i < n; i++) {
if (c[a[i].u] != c[a[i].v]) {
counts++;
degree[a[i].u]++;
degree[a[i].v]++;
}
}
for (int i = 1; i <= n; i++) {
if (counts == degree[i]) {
printf("YES\n%d\n", i);
return 0;
}
}
printf("NO\n");
return 0;
}
/////Runtime error on test
#include < iostream > #include < stdio.h > #include < string.h > using namespace std;
const int maxn = 100005;
struct node {
int u,
v;
}
a[maxn];
int c[maxn],
degree[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) scanf("%d%d", &a[i].u, &a[i].v);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
int ans = 0;
memset(degree, 0, sizeof(degree));
for (int i = 1; i < n; i++) {
if (c[a[i].u] != c[a[i].v]) {
ans++;
degree[a[i].u]++;
degree[a[i].v]++;
}
}
for (int i = 1; i <= n; i++) {
if (ans == degree[i]) {
printf("YES\n%d\n", i);
return 0;
}
}
printf("NO\n");
return 0;
}
来源: http://www.bubuko.com/infodetail-2252123.html