[saikr] 我去前面探探路 树型dp

由题意我们首先可以定义三种状态 dp[u][0]：u节点不放装置时，以该节点为根节点的子树被覆盖所需最小话费。 dp[u][1]：u节点放装置1，以该节点为根的子树被覆盖所需最小话费。 dp[u][2]：u节点放装置2，以该节点为根的子树被覆盖所需最小话费。

那么状态转移很容易想到 如果根节点不放装置，子节点为根节点的树已经被全覆盖的情况下，如何向上递推使根节点与该子节点所连的边被覆盖。很明显子节点必须放装置1或2。 d p [ u ] [ 0 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] ) {dp[u][0]+=min(dp[v][1],dp[v][2])} dp[u][0]+=min(dp[v][1],dp[v][2])（v是u的所有子节点）

剩下两种情况同理易推 d p [ u ] [ 1 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] ) {dp[u][1]+=min(dp[v][1],dp[v][2],dp[v][0])} dp[u][1]+=min(dp[v][1],dp[v][2],dp[v][0]) d p [ u ] [ 2 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] ) {dp[u][2]+=min(dp[v][1],dp[v][2],dp[v][0])} dp[u][2]+=min(dp[v][1],dp[v][2],dp[v][0])

但是注意当u选择装置2时，它有可能直接递推到孙子节点越过儿子节点。 言外之意，我们只需u节点的所有孙子节点为根的子树被覆盖时，也可以完成递推。

所以此时我们需要另外一种状态 dp[u][3]：该节点的所有儿子节点为根的子树被覆盖所需最小话费。

那么dp[u][2]的状态转移还需加上dp[v][3]。 d p [ u ] [ 2 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] , d p [ v ] [ 3 ] ) {dp[u][2]+=min(dp[v][1],dp[v][2],dp[v][0],dp[v][3])} dp[u][2]+=min(dp[v][1],dp[v][2],dp[v][0],dp[v][3])

很容易想出dp[u][3]的转移方程 d p [ u ] [ 3 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] ) {dp[u][3]+=min(dp[v][1],dp[v][2],dp[v][0])} dp[u][3]+=min(dp[v][1],dp[v][2],dp[v][0])

现在状态转移已经全部出来了： d p [ u ] [ 0 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] ) {dp[u][0]+=min(dp[v][1],dp[v][2])} dp[u][0]+=min(dp[v][1],dp[v][2]) d p [ u ] [ 1 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] ) {dp[u][1]+=min(dp[v][1],dp[v][2],dp[v][0])} dp[u][1]+=min(dp[v][1],dp[v][2],dp[v][0]) d p [ u ] [ 2 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] , d p [ v ] [ 3 ] ) {dp[u][2]+=min(dp[v][1],dp[v][2],dp[v][0],dp[v][3])} dp[u][2]+=min(dp[v][1],dp[v][2],dp[v][0],dp[v][3]) d p [ u ] [ 3 ] + = m i n ( d p [ v ] [ 1 ] , d p [ v ] [ 2 ] , d p [ v ] [ 0 ] ) {dp[u][3]+=min(dp[v][1],dp[v][2],dp[v][0])} dp[u][3]+=min(dp[v][1],dp[v][2],dp[v][0])

但是还有一个问题，如果u的子节点v放装置2，那么它和u放装置1是等效的并且此时u是不需要放置1所需的花费v1。 所以我们让其中一个选择装置2花费最小的子节点+dp[u][1]-v1和dp[u][1]进行判断，更新dp[u][1]的值来完成每个状态更新即可。