传送门

首先显然要二分答案。为了判断答案是否可行,我们直接对每棵子树维护一些点对$(u_i,v_i)$,表示可以在第一个点深度为$u_i$,最后一个点深度为$v_i$的情况下走完整棵子树。然后合并两个儿子的时候,用启发式的思想,直接考虑较小的子树中每个点作为起点或终点的情况。这样做的话,每个点维护点对的数量,就是两个儿子中较小的数量乘以2。根据启发式合并的性质,这样做一次是$O(nlogn)$,加上二分答案就是两个log了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 200010
using namespace std;

int n;
int pre[MAXN],ch[MAXN][2];
int size[MAXN],sf[MAXN];
LL v[MAXN],lim;
pair<LL,LL> *f[MAXN];

void dfs(int x){
    if(ch[x][0]){
        dfs(ch[x][0]);
        dfs(ch[x][1]);
        if(size[ch[x][0]]>size[ch[x][1]]) swap(ch[x][0],ch[x][1]);
        size[x]=size[ch[x][0]]<<1;
    }else{
        size[x]=1;
    }
    f[x]=new pair<LL,LL>[size[x]+1];
}

int join(pair<LL,LL> *fs,pair<LL,LL> *f0,pair<LL,LL> *f1,int sf0,int sf1){
    int now0=1,now1=1;
    int sfs=0;
    while(now0<=sf0 || now1<=sf1){
        if(now1>sf1){
            if(!sfs || fs[sfs].second>f0[now0].second)
                fs[++sfs]=f0[now0];
            now0++;
        }else if(now0>sf0){
            if(!sfs || fs[sfs].second>f1[now1].second)
                fs[++sfs]=f1[now1];
            now1++;
        }else if(f0[now0].first<f1[now1].first){
            if(!sfs || fs[sfs].second>f0[now0].second)
                fs[++sfs]=f0[now0];
            now0++;
        }else{
            if(!sfs || fs[sfs].second>f1[now1].second)
                fs[++sfs]=f1[now1];
            now1++;
        }
    }
    return sfs;
}

bool gao(int x){
    if(!ch[x][0]){
        sf[x]=1;
        f[x][1]=make_pair(0,0);
        return 1;
    }
    int c0=ch[x][0],c1=ch[x][1];
    if(!gao(c0)) return 0; 
    if(!gao(c1)) return 0;
    LL delta=v[c0]+v[c1];
    static pair<LL,LL> f0[MAXN],f1[MAXN];
    int sf0=0,sf1=0;
    int now=sf[c1];
    for(int i=sf[c0];i>=1;i--){
        while(now && f[c0][i].second+f[c1][now].first+delta>lim) now--;
        if(!now) break;
        f0[++sf0]=make_pair(f[c0][i].first+v[c0],f[c1][now].second+v[c1]);
    }
    for(int i=1;i<=sf0;i++)
        if(i<sf0-i+1)
            swap(f0[i],f0[sf0-i+1]);
    now=1;
    for(int i=1;i<=sf[c0];i++){
        while(now<=sf[c1] && f[c0][i].first+f[c1][now].second+delta>lim) now++;
        if(now>sf[c1]) break;
        f1[++sf1]=make_pair(f[c1][now].first+v[c1],f[c0][i].second+v[c0]);
    }
    sf[x]=join(f[x],f0,f1,sf0,sf1);
    return sf[x];
}

bool check(LL _lim){
    lim=_lim;
    return gao(1);
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d%lld",pre+i,v+i);
        if(!ch[pre[i]][0]) ch[pre[i]][0]=i;
        else ch[pre[i]][1]=i;
    }
    dfs(1);
    LL l=0,r=131072LL*131072LL;
    while(l<r){
        LL mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}