题意:
给定一棵树,每个点带有各自的颜色,问是否能找出一个点当做根节点,并且它的子树颜色都是相同的。
思路:每颗子树之间的边的两端都是相同的颜色,对不同颜色的答案和是没有贡献的,那么如果找到两端颜色不同的就让不同边数++,两端点都++,如果有个点他的val值等于不同边的总数,那么它一定可以当做根节点了,因为子树中没有点对对答案造成影响。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N];
int c[N];
int kind;
vector<pair<int,int>>query;
int main()
{
int n;
cin >>n;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
query.push_back({
a,b});
}
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
for(auto x:query)
{
int a=x.first;
int b=x.second;
if(c[a]!=c[b])
{
kind++;
h[a]++;
h[b]++;
}
}
for(int i=1;i<=n;i++)
{
if(h[i]==kind)
{
cout<<"YES"<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<"NO"<<endl;
return 0;
}