P 4438[HNOI/AHOI 2018]道路

この問題は木のdpに基づいていくつかの操作を追加しましたが、前処理をしてからテンプレートとあまり差がありません.

#include
#include
#define neko 100010
#define chkmin(a,b) ((a)=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
",dp[dfn[1]][0][0]);
    return 0;
}

　　
転載先:https://www.cnblogs.com/hahaha2124652975/p/11243505.html