Codeforces765E dfs

题意

题意:每次从一棵树中找两根长度相同、起点相同的直链并删去其中一根。重复这个操作,求可以得到的最短直链的长度。如果无法得到直链,输出-1。
需要注意的是树即使已经被删成直链了,如果长度是偶数还可以继续删的。

思路

问题的关键是找到树中的“特殊点”,也就是我上面的图中的所有红点。“特殊点”的特点是它的度>2,且与它相连的直链长度不全相等,即以它为起点,不经过其他度>2的点,到达叶子节点的路径有至少两条,且长度不全相等。
容易看出:若特殊点超过1个,结果必是-1;如果上述路径有三种及以上的长度,结果也是-1。不然,结果就是这两种长度之和,然后再除2直到不为偶数。
看出这个结论后就非常简单了:先对任一点建dfs树,用set存起每个点的节点的返回值,如果set.size>=3直接-1,如果==2就说明这个点是特殊点,再以这个点为起点建树做一遍。如果==1说明是普通点,直接+1返回上一层。
此外还需判断没有特殊点的情况。答案不一定直接就是cut(N-1),比如

4 4 1 4 2 4 3
这种数据,还得瞎搞一下,不再赘述。

AC代码