codeforces 763A Timofey and a tree

题目链接：http://codeforces.com/PRoblemset/problem/763/A

题意：在一棵树中选择一个顶点为根结点，从而使这棵树除根结点以外的所有子树内的颜色一致

        解题入口 ：若一条边关联的两个顶点颜色不同，则根结点必在两者中产生，不然则无解——两者若没有其一上升为根结点，则两者必共存于同一颗子树中，颜色不同，此时无解。

        全面考虑 4种情况：

                              1.关联不同颜色顶点的边数为0

                              2.关联不同颜色顶点的边数为1

                              3.关联不同颜色顶点的边数为n(n>1)，呈放射式，都有关联到同一个顶点

                              4.关联不同颜色顶点的边数为n(n>1)，呈离散式，没有都关联到同一个顶点

       都符合解题入口的描述。

方法一：找到根节点了 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内容           //                    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;}方法二：数数。。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;}