题意：
给出一棵树，N-1条边 每个边的颜色C[i]。询问是否有一个节点作为根，他所有子树的颜色都相同。
比赛结束好久了，才补题。心酸。
思路：
当时没写出来。也是想的是并查集分类，但是搞了90分钟没出。记录下各位博客学的两种比较好的方法
方法一：
对于两端颜色相同的边不予以判定，而对于颜色不同的边，必定是一个端点作为根进行整合。那么只需要记录下有多少个颜色不同的特殊边，并且对于每种特殊边，节点的度数加一，判断是否有某一节点的度数等于特殊边的条数即可
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <set> #include <vector> #define maxn 100005 using namespace std; const int inf=0x3f3f3f3f; int du[maxn]; int u[maxn],v[maxn],col[maxn]; int main() { int n; cin>>n; for(int i=1;i<n;i++) { cin>>u[i]>>v[i]; } for(int i=1;i<=n;i++) cin>>col[i]; int all=0; for(int i=1;i<n;i++) { if(col [ u[i] ]!= col[ v[i] ]) { all++; du[ u[i] ]++; du[ v[i] ]++; } } for(int i=1;i<=n;i++) { if(du[i]==all) { cout<<"YES"<<endl; cout<<i<<endl; return 0; } } cout<<"NO"<<endl; return 0; }方法二：
将同色的分块，和方法一相同，但是用并查集来将树分块。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <set> #include <vector> #define maxn 100005 using namespace std; const int inf=0x3f3f3f3f; int du[maxn]; int u[maxn],v[maxn],col[maxn],vis[maxn]; int father[maxn]; vector <int > relation[maxn]; int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } int Union(int x,int y) { int rootx=find(x); int rooty=find(y); if(rootx!=rooty) { father[rootx]=rooty; } return 0; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<n;i++) { cin>>u[i]>>v[i]; } for(int i=1;i<=n;i++) cin>>col[i]; int all=0; for(int i=1;i<n;i++) { if(col[u[i]]==col[v[i]]) Union(u[i],v[i]); else all++; } for(int i=1;i<n;i++) { int rootx=find(u[i]); int rooty=find(v[i]); if(rootx!=rooty) { du[u[i]]++; du[v[i]]++; } } for(int i=1;i<=n;i++) { if(du[i]==all) { cout<<"YES"<<endl; cout<<i<<endl; return 0; } } cout<<"NO"<<endl; return 0; }