Category:AHOIBZOJDP/动态规划HNOI洛谷省选专题树形DP
Article From:https://www.cnblogs.com/luyouqi233/p/9125158.html

https://www.lydsy.com/JudgeOnline/problem.php?id=5290

https://www.luogu.org/problemnew/show/P4438

It’s really not a difficult problem.

——————————————————

First, the time of the slots (slightly over):

Let f[i][j][k] be the minimum value of the j road in the subtree with I as the root of the K railway.

And then DFS can pass… But the DFS that I think may have a lot to store… I think the solution is not so troublesome.

——————————————————

Set f[i][j][k] to represent I subtree leaves to 1 node distance J road does not repair the minimum value of K railway maintenance.

Then set l=s[u], r=t[u], then f[u][i][j]=min (f[l][i+1][j]+f[r][i][j], f[l][i][j]+f[r][i][j+1]);

Of course, the f array is large, but it is found that some states are running out, so it can be garbage collected.

```#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int N=4e4+5;
int X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
int n,tot,s[N],t[N],dfn[N];
ll a[N],b[N],c[N],f[110][41][41];
stack<int>bin;
void dfs(int u,int x,int y){
if(u<n){
dfs(s[u],x+1,y);dfs(t[u],x,y+1);
}
if(bin.empty())dfn[u]=++tot;
else{dfn[u]=bin.top();bin.pop();}
if(u<n){
bin.push(dfn[s[u]]);bin.push(dfn[t[u]]);
}else{
for(int i=0;i<=40;i++)
for(int j=0;j<=40;j++)
f[dfn[u]][i][j]=c[u]*(a[u]+i)*(b[u]+j);
return;
}
int l=dfn[s[u]],r=dfn[t[u]],k=dfn[u];
for(int i=0;i<=x;i++)
for(int j=0;j<=y;j++)
f[k][i][j]=min(f[l][i+1][j]+f[r][i][j],f[l][i][j]+f[r][i][j+1]);
}
int main(){
for(int i=1;i<n;i++){
if(s[i]<0)s[i]=-s[i]+n;
if(t[i]<0)t[i]=-t[i]+n;
}
dfs(1,0,0);
printf("%lld\n",f[dfn[1]][0][0]);
return 0;
}```

+++++++++++++++++++++++++++++++++++++++++++