Vanya wants to minimize a tree. He can perform the following Operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length a0?=?v, a1, ..., ak, and b0?=?v, b1, ..., bk. Additionally, vertices a1, ..., ak, b1, ..., bk must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices b1, ..., bk can be effectively erased:

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.

The first line of input contains the number of vertices n (2?≤?n?≤?2·105).

Next n?-?1 lines describe edges of the tree. Each of these lines contains two space-separated integers u and v (1?≤?u,?v?≤?n, u?≠?v) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.

If it is impossible to obtain a path, PRint -1. Otherwise, print the minimum number of edges in a possible path.

61 22 32 44 51 6output
3input
71 21 33 41 55 66 7output
-1Note
In the first sample case, a path of three edges is obtained after merging paths 2?-?1?-?6 and 2?-?4?-?5.
It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1?-?3?-?4 and 1?-?5?-?6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.
題意：
給你一棵樹，你可以在這棵樹上進(jìn)行若干次操作，每次操作可以把兩條相同的鏈，根據(jù)一個中點合并在一起，然后問你經(jīng)過若干次合并之后，最后的最短鏈長度是多少。如果不能合并成一條鏈，輸出-1。
題解：
樹形dp。
從節(jié)點1開始dfs，用set去保存一個節(jié)點有多少種深度的子樹。
那么，對于每一個節(jié)點：
1. 如果s.size()==0，那么當(dāng)前節(jié)點就是沒有子樹，也就是這個節(jié)點就是一條鏈中的一個端點，那就是不能縮成一條鏈啦。
2. 如果s.size()==1，那么當(dāng)前的節(jié)點有且只有一種深度的子樹，那么就可以將此時的所有子樹合成一棵樹。這條鏈的長度就是當(dāng)前的深度咯。
3.如果s.size()==2，并且fa==0即沒有父親時，那么我們就找到了一條鏈了，就把這2種深度加起來就是這條鏈的長度咯。
4.如果s.size()==2，并且fa!=0即有父親時，那么這條鏈就會多出父結(jié)點那部分，還沒搜完啊！這時我們要對當(dāng)前的節(jié)點再dfs一遍。
5.如果s.size()>2，當(dāng)前節(jié)點有3種深度的子樹？這時無解啊，直接輸出-1就可以了。
6.如果最終鏈的長度是偶數(shù)，肯定不是最短啦，那么我們要考慮在最中間的那個點作為根，再將兩側(cè)的單鏈繼續(xù)合并。直到最短鏈的長度為奇數(shù)為止。
AC代碼：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 2e5 + 10;vector<int> G[N];int root;int dfs(int cur, int fa){    set<int>s;    for(auto v: G[cur])    {    	if(v!=fa){    		int tmp = dfs(v,cur);    		if(tmp==-1)return -1;    		else s.insert(tmp+1);		}	}	if(s.size() == 0) return 0;	else if(s.size() == 1) return *s.begin();	else if(s.size() == 2 && fa == 0) return *s.begin()+*s.rbegin();	else if(s.size()==2 && fa!=0)	{		root = cur;		return -1;	}	else if(s.size()>2)return -1;}int main(){    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);    }   int ans= dfs(1,0);   if(ans==-1 && root) ans = dfs(root,0);   while(ans%2==0){   	ans/=2;   }   return 0*printf("%d/n",ans);}/*61 22 32 44 51 631111 96 77 18 115 63 59 310 82 44 105*/