Codeforces Round #397 E. Tree Folding （树形dp）

Bertha 。 2022-07-12 08:51 166阅读 0赞

E. Tree Folding

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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 *a*0 = *v*, *a*1, ..., *a**k*, and *b*0 = *v*, *b*1, ..., *b**k*. Additionally, vertices *a*1, ..., *a**k*, *b*1, ..., *b**k* 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 *b*1, ..., *b**k* can be effectively erased:

![faf342095cfdb6f566d6fed24d5c0b2dbf924d49.png][]

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.

Input

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.

Output

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

Examples

input

6
    1 2
    2 3
    2 4
    4 5
    1 6

output

input

7
    1 2
    1 3
    3 4
    1 5
    5 6
    6 7

output

-1

Note

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.

题意：

给你一棵树，你可以在这棵树上进行若干次操作，每次操作可以把两条相同的链，根据一个中点合并在一起，  
然后问你经过若干次合并之后，最后的最短链长度是多少。如果不能合并成一条链，输出-1。

题解：

树形dp。

从节点1开始dfs，用set去保存一个节点有多少种深度的子树。

那么，对于每一个节点：

1. 如果s.size()==0，那么当前节点就是没有子树，也就是这个节点就是一条链中的一个端点，那就是不能缩成一条链啦。

2. 如果s.size()==1，那么当前的节点有且只有一种深度的子树，那么就可以将此时的所有子树合成一棵树。这条链的长度就是当前的深度咯。

3.如果s.size()==2，并且fa==0即没有父亲时，那么我们就找到了一条链了，就把这2种深度加起来就是这条链的长度咯。

4.如果s.size()==2，并且fa!=0即有父亲时，那么这条链就会多出父结点那部分，还没搜完啊！这时我们要对当前的节点再dfs一遍。

5.如果s.size()>2，当前节点有3种深度的子树？这时无解啊，直接输出-1就可以了。

6.如果最终链的长度是偶数，肯定不是最短啦，那么我们要考虑在最中间的那个点作为根，再将两侧的单链继续合并。直到最短链的长度为奇数为止。

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);
    }
    /*
    6
    1 2
    2 3
    2 4
    4 5
    1 6
    
    3
    
    11
    11 9
    6 7
    7 1
    8 11
    5 6
    3 5
    9 3
    10 8
    2 4
    4 10
    
    5
    */

[faf342095cfdb6f566d6fed24d5c0b2dbf924d49.png]: /images/20220710/c9a57622f6524b52a1c9adb685cd0695.png