Each New Year Timofey and his friends cut down a tree of n vertices and bring it home. After that they paint all the n its vertices, so that the i-th vertex gets color ci.

Now it's time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.

Timofey doesn't like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex.

A subtree of some vertex is a subgraph containing that vertex and all its descendants.

Your task is to determine if there is a vertex, taking which in hands Timofey wouldn't be annoyed.

The first line contains single integer n (2?≤?n?≤?105) — the number of vertices in the tree.

Each of the next n?-?1 lines contains two integers u and v (1?≤?u,?v?≤?n, u?≠?v), denoting there is an edge between vertices u and v. It is guaranteed that the given graph is a tree.

The next line contains n integers c1,?c2,?...,?cn (1?≤?ci?≤?105), denoting the colors of the vertices.

PRint "NO" in a single line, if Timofey can't take the tree in such a way that it doesn't annoy him.

Otherwise print "YES" in the first line. In the second line print the index of the vertex which Timofey should take in hands. If there are multiple answers, print any of them.

41 22 33 41 2 1 1output
YES2input
31 22 31 2 3output
YES2input
41 22 33 41 2 1 2output
NO
題意：簡述就是說給我們一個樹：樹中有n個節點，每個節點都會有一個顏色。（用1~n之間不同的數字表示。）同時還說明了樹中各個節點之間的關系。（用n-1個u,v表示。）現在問我們以哪個節點作為根，可以使得這個根下的所有子樹都為純色。（子樹中的所有節點的顏色都相同。）如果有輸出那個節點，如果存在多個答案只需輸出任意解。如果沒有就輸出“NO”。
思路：這個題應該至少有兩種解法。第一種是假設一個點為根然后用dfs遍歷一遍它的子樹，并且判斷這個子樹是否可以為根就行了。（但是，這種做法寫的不好容易超時。而且代碼實現也比較麻煩，需要先用鄰接表存儲整個樹才行。）第二種是在直接使用結構體存儲n-1對輸入，然后在輸入完顏色之后遍歷一遍數組記錄下每個節點與它相鄰的節點中不同色的數量cnt[i](對于第i個節點有cnt[i]個相鄰節點與節點i的顏色不同。)以及所有相鄰節點中不同色的對數m，最后在遍歷數組cnt，如果存在第i個節點cnt[i]==m。則第i個節點就是那個根，如果不存在那就可以直接輸出“NO”了。因為已經說明了給我們的一定是一個樹，所以，這也就是第二種做法的正確的基本。
     在比賽中我原本是用第一種思路來解的，雖然當時是過了。但是，在重測時卻在在60+組中超時了。雖然第二天我就把我原來的代碼調完AC了。但我還是覺得那個代碼又臭又長，所以，就不放出來了。（第一種思路可以在O(nlongn)時間復雜度內完成。）直接上第二個思路的代碼，代碼相對來說就比較精簡。（第二種思路的時間復雜度是O(n)。）
代碼：
#include<iostream>#include<cstring>#define MAX 100005using namespace std;struct edge{	int a,b;};edge E[MAX];//在這個結構體中用來存儲輸入，a,b之間相連。 int poit[MAX],cnt[MAX];//用poit數組來存儲每個節點的顏色。//cnt存儲與它相鄰的點中顏色不同的數量。 int main(){	int n;	while(cin>>n){		int m=0;		for(int j=1;j<n;j++)			cin>>E[j].a>>E[j].b;		for(int j=1;j<=n;j++)			cin>>poit[j];		memset(cnt,0,sizeof(cnt));		for(int j=1;j<n;j++){			if(poit[E[j].a]!=poit[E[j].b]){				cnt[E[j].a]++,cnt[E[j].b]++;				m++;			}		//m表示的是總對數，因為，輸入不會重復，所以m才可以直接這樣計數。 		}		for(int j=1;j<=n;j++){			if(cnt[j]==m){				cout<<"YES"<<endl<<j<<endl;				goto end;			}		//如果找到了一個cin[j]==m那就找到這個根了。 		}		cout<<"NO"<<endl;		end:;	}} 
總結：  總得來說這個題還是相當好的，目測這個就是正解了。代碼實現沒有什么難度，只是想要想到這一點比較麻煩。即使想不到這個方法。但是，對于一些人來說也可以使用強硬的代碼水平來AC。