題目鏈接：http://codeforces.com/PRoblemset/problem/763/A

題意：在一棵樹中選擇一個頂點為根結(jié)點，從而使這棵樹除根結(jié)點以外的所有子樹內(nèi)的顏色一致

        解題入口 ：若一條邊關(guān)聯(lián)的兩個頂點顏色不同，則根結(jié)點必在兩者中產(chǎn)生，不然則無解——兩者若沒有其一上升為根結(jié)點，則兩者必共存于同一顆子樹中，顏色不同，此時無解。

        全面考慮 4種情況：

                              1.關(guān)聯(lián)不同顏色頂點的邊數(shù)為0

                              2.關(guān)聯(lián)不同顏色頂點的邊數(shù)為1

                              3.關(guān)聯(lián)不同顏色頂點的邊數(shù)為n(n>1)，呈放射式，都有關(guān)聯(lián)到同一個頂點

                              4.關(guān)聯(lián)不同顏色頂點的邊數(shù)為n(n>1)，呈離散式，沒有都關(guān)聯(lián)到同一個頂點

       都符合解題入口的描述。

方法一：找到根節(jié)點了 dfs進行check

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <stack>#include <set>#include <map>using namespace std;#define FOR(i,k,n) for(int i=k;i<n;i++)#define FORR(i,k,n) for(int i=k;i<=n;i++)#define scan(a) scanf("%d",&a)#define scann(a,b) scanf("%d%d",&a,&b)#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)#define mst(a,n)  memset(a,n,sizeof(a))#define ll long long#define N 100005#define mod 1000000007#define INF 0x3f3f3f3fconst double eps=1e-8;const double pi=acos(-1.0);vector<int> g[N];int c[N];int vis[N];int root[2];bool Dfs(int u,int i){    vis[u]=1;                                                           //check流程    for(int j=0; j<g[u].size(); j++)                                    //    {                                                                   //        if(!vis[g[u][j]])                                               //        {                                                               //            if(!Dfs(g[u][j],i))                                         //                return false;                                           //            else                                                        //            {                                                           //                if(u!=root[i] && c[u]!=c[g[u][j]])//check內(nèi)容           //                    return false;                                       //            }                                                           //        }                                                               //    }                                                                   //    return true;                                                        //check流程}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    int n,u,v;    cin>>n;    for(int i=0; i<n-1; i++)    {        cin>>u>>v;        g[u].push_back(v);        g[v].push_back(u);    }    for(int i=1; i<=n; i++)        cin>>c[i];    for(int u=1; u<=n; u++)    {        for(int j=0; j<g[u].size(); j++)            if(c[u]!=c[g[u][j]])                root[0]=u, root[1]=g[u][j];    }    //    //for(int i=0;i<2;i++) cout<<"root "<<root[i]<<endl;    //    if(!root[0]&&!root[1])    {        cout<<"YES"<<endl<<"1"<<endl;        return 0;    }    int i=0;    for(;i<2;i++)    {        mst(vis,0);        if(Dfs(root[i],i))        {            cout<<"YES"<<endl<<root[i]<<endl;            break;        }    }    if(i==2)        cout<<"NO"<<endl;    return 0;}方法二：數(shù)數(shù)。。Orz（在cf上看到別人的做法）
# include<bits/stdc++.h>using namespace std;#define ll long longll arr[1000009];ll brr[1000009];ll idx[1000009];ll st[1000009];int main(){        ll n;        cin>>n;        for(int i=1; i<n; i++)        {            cin>>arr[i]>>brr[i];        }        for(int i=1; i<=n; i++)        {            cin>>idx[i];        }        ll c=0;        for(int i=1; i<n; i++)        {            if(idx[arr[i]]!=idx[brr[i]])            {                c++;                st[arr[i]]++;                st[brr[i]]++;            }        }        for(int i=1; i<=n; i++)        {            if(st[i]==c)            {                cout<<"YES/n"<<i<<endl;                return 0;            }        }        cout<<"NO/n";    return 0;}