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

我去前面探探路 树型dp"/>

[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]的值来完成每个状态更新即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-xconst double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e4+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,v1,v2;
vector<int> g[maxn];
ll d[maxn][4];void dfs(int u,int f)
{d[u][1]=v1,d[u][2]=v2;ll cost=inf;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==f) continue;dfs(v,u);d[u][0]+=min(d[v][1],d[v][2]);d[u][1]+=min(d[v][0],min(d[v][1],d[v][2]));d[u][2]+=min(min(min(d[v][3],d[v][2]),d[v][1]),d[v][0]);d[u][3]+=min(d[v][0],min(d[v][1],d[v][2]));cost=min(cost,d[v][2]-min(d[v][0],min(d[v][1],d[v][2])));}d[u][1]=min(d[u][1],d[u][1]-v1+cost); 
}int main()
{scanf("%d%d%d",&n,&v1,&v2);for(int i=1;i<n;i++){int u,v; scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);ll ans=min(min(d[1][0],d[1][1]),d[1][2]);printf("%lld\n",ans);
}