题解 P4438 【[HNOI/AHOI2018]道路】
teafrogsf
2018-04-17 10:58:59
## 考场上的我是多SB才没想到这题的写法啊......我连树链剖分都没想到啊.....
那么，转移的形式楼下讲的非常清楚了，我主要讲下如何卡空间。
我们可以发现每次$\rm dp$统计答案是自下而上的，所以你当前节点的两个子节点在你这个节点统计完答案后就用不上了。
所以我们可以记录当前节点的$\rm dfn$，然后遍历左儿子$\rm dfn+1$，右儿子$\rm dfn+2$，因为你的叶子节点是直接将所有情况初始化的，所以不用担心转移的点会弄错。
你可以发现这样转移最右边的叶子节点，它的$\rm dfn$也不会超过$\rm 40*2+1$。所以空间就可以满足要求了。
~~不过貌似我初始化的时候没有memset也过了？是数据水还是可以证明不需要啊？不想想了~~
好像速度是全站Rank3的样子。
```cpp
#include<cstdio>
#include<cstring>
#define neko 100010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
int n,a[neko],b[neko],c[neko],dfn[neko],son[neko][2];
long long dp[110][50][50];
void dfs(int u,int now,int rd,int tr)
{
dfn[u]=now;
if(u>=n)//countries are leaves
{
// memset(dp[dfn[u]],0,sizeof(dp[dfn[u]]));
f(i,0,rd)
f(j,0,tr)
dp[dfn[u]][i][j]=1ll*c[u]*1ll*(a[u]+i)*1ll*(b[u]+j);
return;
}
dfs(son[u][0],now+1,rd+1,tr),dfs(son[u][1],now+2,rd,tr+1);
f(i,0,rd)
f(j,0,tr)
dp[dfn[u]][i][j]=chkmin(dp[dfn[son[u][0]]][i][j]+dp[dfn[son[u][1]]][i][j+1],
dp[dfn[son[u][0]]][i+1][j]+dp[dfn[son[u][1]]][i][j]);
}
int main()
{
int x,y;
scanf("%d",&n);
f(i,1,n-1)
{
scanf("%d%d",&x,&y),x=(x<0)?(-x+n-1):x,y=(y<0)?(-y+n-1):y;
son[i][0]=x,son[i][1]=y;
}
f(i,0,n-1)scanf("%d%d%d",&a[i+n],&b[i+n],&c[i+n]);
dfs(1,1,0,0),printf("%lld\n",dp[dfn[1]][0][0]);
return 0;
}
```