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