bzoj3677/洛谷P3647 连珠线 树形dp题目分析代码
题目分析考虑第一颗珠子（根）是谁，那么状态显然是f(x,0/1)，表示x是通过1操作加入的还是通过2操作加入的。如果是通过2操作加入的，那么边(x,father(x))和边(x,son(x))应该是蓝色的。 由此我们可以得到一个枚举根的O(n2)O(n2)O(n^2) dp: (y指的是x的儿子们,w指的是边的长度） f(x,0)=∑max(f(y,0),f(y,1)+w(x,y))f(x...
