懒得复制，戳我戳我

Solution:

• \(dp[i][j][k]\)以\(i\)为子树根节点，到根节点中有\(j\)条公路没修，\(k\)条铁路没修，存子树不便利和
• \(dp[i][j][k]=min(dp[ls][j-1][k]+dp[rs][j][k] , dp[ls][j][k]+dp[rs][j+1][k])\),这个式子其实不难但我感觉也不简单qwq
• 就这样没了

Code:

//It is coded by Ning_Mew on 4.17

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn=2e4+7;

int n;

struct Node{

  int l,r;LL a,b,c;LL dp[40][40];

  Node(){l=r=a=b=c=0;memset(dp,0LL,sizeof(dp));}

}node[maxn*2];

void dfs(int u){

  if(u>n)return;

  int ls=node[u].l,rs=node[u].r;

  dfs(ls);dfs(rs);

  for(int i=0;i<=39;i++){

    for(int j=0;j<=39;j++){

      node[u].dp[i][j]=min(node[ls].dp[i+1][j]+node[rs].dp[i][j] , node[rs].dp[i][j+1]+node[ls].dp[i][j]);

    }

  }return;

}

int main(){

  scanf("%d",&n);

  for(int i=1;i<=n-1;i++){

    int x,y;scanf("%d%d",&x,&y);

    if(x<0)x=-x+n;if(y<0)y=-y+n;

    node[i].l=x;node[i].r=y;

  }

  for(int i=n+1;i<=n+n;i++){

    LL a,b,c;scanf("%lld%lld%lld",&a,&b,&c);

    node[i].a=a;node[i].b=b;node[i].c=c;

    for(int j=0;j<=39;j++){

      for(int k=0;k<=39;k++){

	node[i].dp[j][k]=c*(a+j)*(b+k);

      }

    }

  }

  dfs(1);

  printf("%lld\n",node[1].dp[0][0]);

  return 0;

}