Limak is a little bear who learns to draw. People usually start with houses, fences and flowers but why would bears do it? Limak lives in the forest and he decides to draw a tree.
Recall that tree is a connected graph consisting of n vertices and n - 1 edges.
Limak chose a tree with n vertices. He has infinite strip of paper with two parallel rows of dots. Little bear wants to assign vertices of a tree to some n distinct dots on a paper so that edges would intersect only at their endpoints — drawn tree must be planar. Below you can see one of correct drawings for the first sample test.
Is it possible for Limak to draw chosen tree?
The first line contains single integer n (1 ≤ n ≤ 105).
Next n - 1 lines contain description of a tree. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) denoting an edge between vertices ai and bi. It's guaranteed that given description forms a tree.
Print "Yes" (without the quotes) if Limak can draw chosen tree. Otherwise, print "No" (without the quotes).
8 1 2 1 3 1 6 6 4 6 7 6 5 7 8
Yes
13 1 2 1 3 1 4 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13
No
题目大意：给出一棵树，问能否把它画在一个两行的点阵上，宽度无限制，边与边之间不能交叉。
考虑一颗已经画好的树，取它最左边和最右边的点之间的路径，称为主链。
可以发现空白区域被分成了若干个只有一行的区域。
树的剩余部分就是这条主链上的分叉。分叉只有两种可能：Y形和链。
图中黑色的是主链，左侧的蓝色部分是Y形，右侧是链。
考虑如何确定给出的树是否是“主链+Y形+链”的形式的。分别从树的每个叶节点开始DFS，把经过的节点都打上标记，直到到达一个度超过2的节点。那个节点不大标记，而是记录它的腿数+1，腿指的是向那条边延伸出去只有一条链。注意因为腿最多只有两条，如果腿数超过2了就直接让它等于2。如果一个节点的度数减腿数大于1，那么它一定是主链上的点。显然主链上的点最多只有2个主链上的点和它相连，否则无解。
代码在此。
评论 (0)
