题目大意：
一个完全二叉树上有$n(nle40000)$个结点，每个叶子节点$i$有属性$a_i,b_i,c_i$。对于每个非叶子结点可以选择其中一条向下的边进行标记。若从结点$i$到根的路径上有$x_i$条未标记左向边和$y_i$条未标记右向边，则改标记方案的受益为$sum c_i(a_i+x_i)(b_i+y_i)$。求最大受益。
思路：
用$f[x][i][j]$表示从$x$到根路径上有$i$条未标记左向边和$j$条未标记右向边。则对于叶子节点，$f[x][i][j]=c_x(a_x+i)(b_x+j)$。对于非叶子节点，$f[x][i][j]=min(f[l][i+1][j]+f[r][i][j],f[l][i][j]+f[r][i][j+1])$。答案即为$f[1][0][0]$。
1 #include<cstdio> 2 #include<cctype> 3 #include<algorithm> 4 typedef long long int64; 5 inline int getint() { 6 register char ch; 7 register bool neg=false; 8 while(!isdigit(ch=getchar())) if(ch=='-') neg=true; 9 register int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return neg?-x:x; 12 } 13 int n; 14 inline int getid() { 15 int x=getint(); 16 if(x<0) x=-x+n-1; 17 return x; 18 } 19 const int N=4e4,logN=15; 20 int64 f[N][logN][logN]; 21 int ch[N][2],a[N],b[N],c[N]; 22 void dfs(const int &x,const int &cnt1,const int &cnt2) { 23 if(x>=n) { 24 for(register int i=0;i<=cnt1;i++) { 25 for(register int j=0;j<=cnt2;j++) { 26 f[x][i][j]=(int64)c[x]*(a[x]+i)*(b[x]+j); 27 } 28 } 29 return; 30 } 31 dfs(ch[x][0],cnt1+1,cnt2); 32 dfs(ch[x][1],cnt1,cnt2+1); 33 for(register int i=0;i<=cnt1;i++) { 34 for(register int j=0;j<=cnt2;j++) { 35 f[x][i][j]=std::min(f[ch[x][0]][i+1][j]+f[ch[x][1]][i][j],f[ch[x][0]][i][j]+f[ch[x][1]][i][j+1]); 36 } 37 } 38 } 39 int main() { 40 n=getint(); 41 for(register int i=1;i<n;i++) { 42 ch[i][0]=getid(); 43 ch[i][1]=getid(); 44 } 45 for(register int i=n;i<n*2;i++) { 46 a[i]=getint(); 47 b[i]=getint(); 48 c[i]=getint(); 49 } 50 dfs(1,0,0); 51 printf("%lld ",f[1][0][0]); 52 return 0; 53 }