Description
Solution
树形 DP 裸题，就是拼出两条路径有点麻烦。
参考这篇博客的做法。
设 (dp(i,0)) 表示以 (i) 号点为根的子树中，有一条过根的单链，拆出连通块的数量。注意这里只考虑以 (i) 为根的子树，不算 (i) 的父亲所在的外面那一个大连通块！下面 (3) 个状态同理
(dp(i,1)) 表示以 (i) 号点为根的子树中，有一条不过根的路径，拆出连通块的数量。
(dp(i,2)) 表示以 (i) 号点为根的子树中，有一条过根的路径，拆出连通块的数量。
(dp(i,3)) 表示以 (i) 号点为根的子树种，有一条路径（不管过不过根）和一条过根单链，拆出连通块的数量。
那么答案显然可以用上面 (4) 种状态拼出来。
对着暴力对拍，每拍出一种没考虑到的转移就加上，然后就做完了……
复杂度 (O(n))。