题目概述

有 $n-1$ 座城市，$n$ 个乡村，每个城市有一条公路和一条铁路连进来（乡村没有连进来的路），每个乡村有参数 $a_i,b_i,c_i$ ，如果乡村走到 $1$ 号城市的路径上有 $x$ 条没有翻新的公路和 $y$ 条没有翻新的铁路，就会产生 $(a_i+x)(b_i+y)c_i$ 的代价，现在可以选择 $n-1$ 条路翻新，求最小代价。

解题报告

不难想到DP：$f_{x,i,A,B}$ 表示从根到 $x$ 点，已经翻新了 $A$ 条公路和 $B$ 条铁路，且 $x$ 子树内翻新了 $i$ 条路的最优解。

设最大深度为 $d$ ，这样DP的时间复杂度最好为 $O(n^2d^2)$ ，果断GG了。感性理解一下，路选的越多，收益是越来越少的，所以可以wqs二分去掉 $i$ 那一维，时间复杂度为 $O(nd^2log_2Max)$ ，还是不太行……

这时候我们寻找下性质，根据贪心，如果要选 $i$ 这条公路（铁路），那么 $i$ 上面所有公路（铁路）一定要选，否则肯定不会选 $i$ ，而是选 $i$ 上面的路从而影响更多乡村。

这样的话，我们可以重新设计下状态：$A=-1$ 表示 $x$ 上面的公路全都选了，此时可以选 $x$ 子树中的路；$A\ge 0$ 表示 $x$ 上面的公路选了 $A$ 条，此时不可以选子树中的路。$B$ 同理。

那么一旦 $A=-1$ 或 $B=-1$ ，就只有常数种转移和 $O(d)$ 种状态，但是如果 $A\ge 0,B\ge 0$ 呢？由于 $A\ge0,B\ge0$ ，子树无法再影响当前状态，可以直接得出答案，只需要预处理 $sum_{x,A,B}$ 表示此时的代价即可。

用哈希表记忆化一下，时间复杂度就是 $O(ndlog_2Max+nd^2)$ 。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;typedef pair<LL,int> pli;
const int maxn=20000,maxm=maxn<<1,maxd=40,HA=999917,maxt=2e6;

int n,son[maxn+5][2],a[maxm+5],b[maxm+5],c[maxm+5],SA[maxm+5],SB[maxm+5];
LL sum[maxn+5][maxd+5][maxd+5],L,R,mid;
struct Hashmap{
    int E,lnk[HA],top,stk[HA+5],nxt[maxt+5];pli w[maxt+5];LL son[maxt+5];
    inline void Clear() {E=0;while (top) lnk[stk[top--]]=0;}
    inline void Add(int x,LL y) {son[++E]=y;w[E]=mp(0,0);nxt[E]=lnk[x];lnk[x]=E;}
    inline bool Count(LL x) {for (int j=lnk[x%HA];j;j=nxt[j]) if (son[j]==x) return 1;return 0;}
    inline pli& operator [] (const LL &x){
        int ha=x%HA;for (int j=lnk[ha];j;j=nxt[j]) if (son[j]==x) return w[j];
        if (!lnk[ha]) stk[++top]=ha;Add(ha,x);return w[E];
    }
}f;

void Dfs(int x,int A=0,int B=0){
    SA[x]=A;SB[x]=B;if (x>=n) return;
    Dfs(son[x][0],A+1,B);Dfs(son[x][1],A,B+1);
    for (int i=0,u;i<=40;i++)
        for (int j=0;j<=40;j++){
            if ((u=son[x][0])<n) sum[x][i][j]+=sum[u][i][j];
            else if (A+1>=i&&B>=j) sum[x][i][j]+=(LL)(a[u]+A+1-i)*(b[u]+B-j)*c[u];
            if ((u=son[x][1])<n) sum[x][i][j]+=sum[u][i][j];
            else if (A>=i&&B+1>=j) sum[x][i][j]+=(LL)(a[u]+A-i)*(b[u]+B+1-j)*c[u];
        }
}
inline pli operator + (const pli &a,const pli &b) {return mp(a.fr+b.fr,a.sc+b.sc);}
inline void Fmin(LL &F,int &G,pli a,int b){
    a.fr+=mid*b;a.sc+=b;
    if (a.fr<F||a.fr==F&&a.sc<G) F=a.fr,G=a.sc;
}
#define Hash(x,A,B) ((LL)(x)*400040001+(A)*20001+(B))
pli DP(int x,int A=-1,int B=-1){
    if (x>=n){
        if (A<0&&B<0) return mp((LL)a[x]*b[x]*c[x],0);
        if (A<0&&~B) return mp((LL)a[x]*(b[x]+SB[x]-B)*c[x],0);
        if (~A&&B<0) return mp((LL)(a[x]+SA[x]-A)*b[x]*c[x],0);
        return mp((LL)(a[x]+SA[x]-A)*(b[x]+SB[x]-B)*c[x],0);
    }if (~A&&~B) return mp(sum[x][A][B],0);if (f.Count(Hash(x,A,B))) return f[Hash(x,A,B)];
    LL &F=f[Hash(x,A,B)].fr;int &G=f[Hash(x,A,B)].sc;F=1e18;G=1e9;
    if (A<0&&B<0){
        Fmin(F,G,DP(son[x][0],-1,-1)+DP(son[x][1],-1,-1),2);
        Fmin(F,G,DP(son[x][0],SA[x],-1)+DP(son[x][1],-1,-1),1);
        Fmin(F,G,DP(son[x][0],-1,-1)+DP(son[x][1],-1,SB[x]),1);
        Fmin(F,G,DP(son[x][0],SA[x],-1)+DP(son[x][1],-1,SB[x]),0);
    }
    if (A<0&&~B){
        Fmin(F,G,DP(son[x][0],-1,B)+DP(son[x][1],-1,B),1);
        Fmin(F,G,DP(son[x][0],SA[x],B)+DP(son[x][1],-1,B),0);
    }
    if (~A&&B<0){
        Fmin(F,G,DP(son[x][0],A,-1)+DP(son[x][1],A,-1),1);
        Fmin(F,G,DP(son[x][0],A,-1)+DP(son[x][1],A,SB[x]),0);
    }return mp(F,G);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<n;i++){
        scanf("%d%d",&son[i][0],&son[i][1]);
        if (son[i][0]<0) son[i][0]=n-1-son[i][0];if (son[i][1]<0) son[i][1]=n-1-son[i][1];
    }for (int i=n;i<(n<<1);i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);Dfs(1);L=0;R=1e15;
    while (L<=R) (mid=L+(R-L>>1),f.Clear(),DP(1).sc)<=n-1?R=mid-1:L=mid+1;
    mid=L;f.Clear();printf("%lld\n",DP(1).fr-L*(n-1));return 0;
}