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