题目描述：
题解：
二分+暴力$vector$+$dfs$。
记录下所有可能的子树内合法方案，双指针+归并合并。
代码：
#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 200050; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int n,fa[N],ch[N][2]; ll v[N],dep[N]; void DFS(int u) { if(!ch[u][0])return ; dep[ch[u][0]]=dep[u]+v[ch[u][0]],DFS(ch[u][0]); dep[ch[u][1]]=dep[u]+v[ch[u][1]],DFS(ch[u][1]); } struct Pair { ll x,y; Pair(){} Pair(ll x,ll y):x(x),y(y){} }g1[N],g2[N],g[N]; vector<Pair>ve[N]; ll mid; int Merge(int len) { int i = 1,j = len,k = 0; while(i<=len&&j>=1) { if(g1[i].x<=g2[j].x)g[++k]=g1[i++]; else g[++k]=g2[j--]; } while(i<=len)g[++k]=g1[i++]; while(j>=1)g[++k]=g2[j--]; return k; } void dfs(int u) { if(!ch[u][0]){ve[u].push_back(Pair(dep[u],dep[u]));return ;} int ls = ch[u][0],rs = ch[u][1]; dfs(ls),dfs(rs);int k=0; if(ve[ls].size()>ve[rs].size())swap(ls,rs); for(int i=0,j=-1,l1=ve[ls].size(),l2=ve[rs].size();i<l1;i++) { while(j<l2-1&&ve[ls][i].y+ve[rs][j+1].x-2ll*dep[u]<=mid)j++; if(~j)g1[++k]=Pair(ve[ls][i].x,ve[rs][j].y),g2[k]=Pair(ve[rs][j].y,ve[ls][i].x); } int len = Merge(k); for(int i=1;i<=len;i++) if(i==1||g[i].y<g[i-1].y) ve[u].push_back(g[i]); } bool check() { for(int i=1;i<=n;i++) ve[i].clear(); dfs(1); return (int)ve[1].size()>0; } int main() { read(n); for(int i=2;i<=n;i++) { read(fa[i]),read(v[i]); if(!ch[fa[i]][0])ch[fa[i]][0]=i; else ch[fa[i]][1]=i; } DFS(1); ll l = 0,r = 200000ll*n,ans = r; while(l<=r) { mid = (l+r)>>1; if(check())ans=mid,r=mid-1; else l=mid+1; } printf("%lld ",ans); return 0; }