【每日一题】树

Step 0

原本错误思路：模拟染色过程。
把树构建出来，由题意初步模拟为，为了使同颜色（x，y）任意两点到达对方，应该由根结点开始染色，但凡染出一条路径，该根的其他结点则只有两个选择：染同样的颜色或必须换新颜色。每遇到一个根结点（分岔口）都会面临这样的选择。即时统计染色点数，看是否染完。
1）复杂度近似2^n。
2）构建树有困难，需要确定根结点才能确定父子的方向。但树的输入又是无向的，以邻接链表储存会无法分清其父其子。而模拟的染色是父向子的方向。

Step 1

题目是求解染色方案数，并不在意实际染色情况，尝试把题目抽象成数字。
以上述的根向其子结点染色的过程面临的不同选择，即是可能的新方案数。
所以应该把每次的新方案数都累计起来。
故需遍历该树一遍，以累计。
如何遍历？实打实地遍历一遍又要建树，

总之假装遍历，把选择累计
https://blog.nowcoder.net/n/a628960724c74b838b35f4c1d4b9617f
或选择断路
https://blog.nowcoder.net/n/c76751c0215344ff99357aaee5235851