定义出状态然后自下而上dp。
状态为 以第 i 个节点为根 涂 j 颜色情况下的方案数。
如果当前已经指定颜色，那么其他颜色数就为0.
状态转移方程：
f
u
,
j
=
∑
v
=
s
o
n
u
,
k
≠
j
f
v
,
k
f_{u,j}=\sum_{v=son_u,k≠j}f_{v,k}
fu,j=v=sonu,k=j∑fv,k
细节：取模开long long。
一个点可以被儿子观察到，可以被自己观察到，可以被父亲节点观察到。
设状态为以 i 为根节点 被 0,1,2(儿，自己，父) 观察到所用到的最少节点数。
当前节点观察到自己，那么儿子什么状态都无所谓。
f
u
,
1
=
1
+
∑
m
i
n
(
f
v
,
0
,
f
v
,
1
,
f
v
,
2
)
f_{u,1}=1+\sum min(f_{v,0},f_{v,1},f_{v,2})
fu,1=1+∑min(fv,0,fv,1,fv,2)
当前节点被父亲观察到，儿子要么被孙子观察到，要么自己观察自己。
f
u
,
2
=
∑
m
i
n
(
f
v
,
0
,
f
v
,
1
)
f_{u,2}=\sum min(f_{v,0},f_{v,1})
fu,2=∑min(fv,0,fv,1)
当前节点被儿子观察到，选择其中一个儿子观察自己，其余取最小值。而后面的\sum min(…) 已经被计算过，保存在fu,2里，消除当前点的影响然后加上fv,1即可。由于fu,0是取min，所以初始化要为无穷大。
f
u
,
0
=
m
i
n
(
f
v
i
,
1
+
∑
m
i
n
(
f
v
j
,
0
,
f
v
j
,
1
)
)
f_{u,0}=min(f_{v_i,1}+\sum min(f_{v_j,0},f_{v_j,1}))
fu,0=min(fvi,1+∑min(fvj,0,fvj,1))
code
错误思路：每次贪心的剪去一枝，剪两次。但是贪的不彻底，应该是自底部往上贪，而不是自上而下。因为当前节点满足，删除后，可能它的父节点也满足；或者当前子节点满足了，父节点删除了它之后又不满足了。最简单的办法就是删除当前节点，然后再跑一遍。WAcode
自底向上检查当前节点，如果满足那么删除当前节点。然后重新跑一遍求和和查找。复杂度O(4n).
fi,j表示为 i 节点到 j 节点的最大分数。rti,j 为[l,r]这个节点取最大值时，它的根节点，用于先序遍历。不太能算作是dp题目，应该是搜索 + 数据结构。
首先建树，其次处理好儿子在dp过程中会用到，我是在dfs过程中保存儿子。状态定义为 1)f： 以 i 为根节点且 i 为 0,1,2 颜色的子树中绿色最多个数。2)g： 以 i 为根节点且 i 为 0,1,2 颜色的子树中绿色最少个数。0,1,2为红蓝绿。
状态转移方程：其他颜色轮换一下就行了。
f
u
,
0
=
m
a
x
(
f
v
1
,
1
/
2
+
f
v
2
,
2
/
1
)
;
f
u
,
0
=
m
a
x
(
f
v
1
,
1
/
2
)
f_{u,0}=max(f_{v_1,1/2}+f_{v_2,2/1});f_{u,0}=max(f_{v_1,1/2})
fu,0=max(fv1,1/2+fv2,2/1);fu,0=max(fv1,1/2)
最少个数也同理。
g
u
,
0
=
m
i
n
(
g
v
1
,
1
/
2
+
g
v
2
,
2
/
1
)
;
g
u
,
0
=
m
i
n
(
g
v
1
,
1
/
2
)
g_{u,0}=min(g_{v_1,1/2}+g_{v_2,2/1});g_{u,0}=min(g_{v_1,1/2})
gu,0=min(gv1,1/2+gv2,2/1);gu,0=min(gv1,1/2)
code
背包循环顺序为物品，数量，决策。数量倒序。
总共n门课，选择m门，使得学分和最大。但是课程含有先后关系，每门课至多有一个先前的课。
由于每门课至多有一个先前的课，明显是树形关系。选择m门那么背包容量就是m，每门课体积是1.背包价值是学分之和。
为了计算方便，加一个超级源点，总根权值为0。状态转移方程：
f
u
,
j
=
m
a
x
(
f
u
,
j
−
k
+
f
v
,
k
)
f_{u,j}=max(f_{u,j-k}+f_{v,k})
fu,j=max(fu,j−k+fv,k)
由于当前根节点被选入，最后倒序插入当前点。
与上一题不同，此题是边权。所以最后没有for ( i = m; i > 0; i–)插入当前节点权值的操作。其他基本一致。
状态转移方程：
f
u
,
j
=
m
a
x
(
f
u
,
j
−
k
−
1
+
f
v
,
k
+
w
i
)
f_{u,j}=max(f_{u,j-k-1}+f_{v,k}+w_i)
fu,j=max(fu,j−k−1+fv,k+wi)
code
边可以重复利用，但只需要付一次费用。
以 i 为根的子树中，选择 j 个用户的最大收益。最后选择值大于等于0的即可。
f
u
,
j
=
m
a
x
(
f
u
,
j
−
k
+
f
v
,
k
−
w
i
)
f_{u,j}=max(f_{u,j-k}+f_{v,k}-w_i)
fu,j=max(fu,j−k+fv,k−wi)
code
给定一棵树，每个节点有一个优惠券，如果使用了优惠券，那么父节点也必须使用优惠券。使用优惠券的节点必须购买。不使用优惠券怎么买都行。
由于b <= 1e9。所以只能枚举数量，跟上一题类似。f[i][j][2]表示以 i 为根的子树用/不用优惠券购买 j 个节点的最小价值。
状态转移方程：
f
u
,
i
+
j
,
0
=
m
i
n
i
≤
d
o
n
e
,
j
≤
s
z
[
v
]
(
f
u
,
i
,
0
+
f
v
,
j
,
0
)
f_{u,i+j,0}=\underset {i≤done,j≤sz[v]}{min} (f_{u,i,0}+f_{v,j,0})
fu,i+j,0=i≤done,j≤sz[v]min(fu,i,0+fv,j,0)
f u , i + j , 1 = m i n i ≤ d o n e , j ≤ s z [ v ] ( f u , i , 1 + ( f v , j , 0 , f v , j , 1 ) ) f_{u,i+j,1}=\underset {i≤done,j≤sz[v]}{min} (f_{u,i,1}+(f_{v,j,0},f_{v,j,1})) fu,i+j,1=i≤done,j≤sz[v]min(fu,i,1+(fv,j,0,fv,j,1))
背包合并过程，每来一个儿子就把它跟之前已经合并好的背包合并，最终合并成一个包，运用的是顺推，和之前不同。
细节：初始化为无穷大，f1,0,1不是0，循环倒序。初始化用memset，用for会TLE。f 边缘情况赋值要正确。
建边是dfs建边。另外，源点要新开一个表示起始点。背包合并过程中，会有从一个叶子出来到另一个叶子的情况，边权要乘以2。题目描述是“警察到来之前”，应该是小于t，而不是小于等于。
背包为 以 i 为根节点保留 j 个点所删除的最少边。由于根节点是必选的，所以选择儿子就减去一条边(边权为负)。一开始想的是删除p个点，想错了。
f
u
,
i
=
m
i
n
(
f
u
,
i
−
j
+
f
v
,
j
−
1
)
f_{u,i}=min(f_{u,i-j}+f_{v,j}-1)
fu,i=min(fu,i−j+fv,j−1)
code
换根dp一般分为三个步骤：
1、先指定一个根节点
2、一次dfs统计子树内的节点对当前节点的贡献
3、一次dfs统计父亲节点对当前节点的贡献并合并统计最终答案
设 v 点以下节点深度之和为gv,大小为szv,把v当做新根时深度之和为fv。
计算fv要加上自己的贡献和父节点对自己的贡献。
fv=gv + (fu - (gv + sz[v])) + (n - sz[v]) = fu - sz[v] * 2 + n.
跟上一题的思路基本一致。设 v 点以下节点反边数量之和为gv,把v当做新根时深度之和为fv。mp(u,v),mp(v,u)位置特殊，fu减去gv时，u->v边没处理，要看它是否是正边，正边不用管，反边减一。当 v 做根节点时，同理判断v->u点。
fv = gv + (fu - gv - mp(v,u)) + mp(u,v) = fu - mp(v,u) + mp(u,v).
跟上一题思路基本一致。记得开long long.
fv = gv + (fu - gv - sumv * w) + (nc - sumv) * w = fu + (nc - sumv * 2) * w.
一开始写的是总和，结果错了。应该分成k个状态，每个节点都要对 k 个状态单独转移。最后算一下总和即可。把这个问题看成是距离 i 为 j 的节点权值之和，这个 j 有 k 个。如果没有 k 个，那么这个问题是很好解决的，加了 k 个以后就会想多。做法就是对距离 j 转换，转换 k 次，最后求和。
f
v
,
j
=
g
v
,
j
−
g
j
−
2
+
f
u
,
j
−
1
f_{v,j}=g_{v,j}-g_{j-2}+f_{u,j-1}
fv,j=gv,j−gj−2+fu,j−1
code