this is not a 正经的note
you may not understand
Problem 1:二叉树，有权，要选它父亲才能选它，$n\leq200,m\leq500$
I: $dp_{i,j}$表示现在到达第i号节点，用掉j个容量，瞎搞
$dp[r][i]$表示以r为根的子树，总重量为i,子树的总价值
若选择r,则$max(dp[r->左][j]+dp[r->右][i-j-w[r]]+v[r])$
注意只能是子树
时间复杂度:$O(nm^2)$
若为多叉树:
g[r][i]表示r和所有右兄弟子树，f只表示自己的子树
g(r)=f(r)+g(s) s为它的右兄弟
f(r)->转移成第一个左儿子的r
g(r)->转移成它的右兄弟的g与自己的f
一个定义它自己的子树，第二个定义与自己兄弟的森林
先想二叉情况，再套两个转移，大多情况可以解决
加强版:n<=2000,m<=5000
若不选节点，转移兄弟
若选他，则转移他的儿子
性质:在一棵树上做x条不想交的道路，则一个节点最多与两条道路相连
先考虑二叉树情况：
F(v,i) v到每一个节点的最大值，i表示是否与v的父亲相连
则：
F[v][0]=min max(f[v->left or right][0 or 1]+1or 0)
F[v][1]:
- f[left][0]+1,f[right][1]
- 1 0+1
- 0+1 0+1
多叉树
F指父亲，g指自森林有几个连接到自己的父亲
F->g g->f
一棵树，权值，求一个长度为k的联通块权值最大
随便选一个为根，然后做背包即可