#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define X first
#define Y second
const int maxn=131072+233;
int n,fa[maxn],lc[maxn],rc[maxn],w[maxn];
LL mid;
vector<pair<LL,LL> > S[maxn],tmp;
void dfs(int u)
{
if (!lc[u])
{
S[u].push_back(make_pair(w[u],w[u]));
return;
}
dfs(lc[u]); dfs(rc[u]);
int i,j=-1;
int m=(int)S[rc[u]].size()-1;
for (i=0;i<(int)S[lc[u]].size();i++)
{
bool flag=0;
while (j<m&&S[lc[u]][i].Y+S[rc[u]][j+1].X<=mid) j++,flag=1;
if (flag)
S[u].push_back(make_pair(S[lc[u]][i].X+w[u],S[rc[u]][j].Y+w[u]));
}
m=(int)S[u].size();
for (i=0;i<m;i++)
S[u].push_back(make_pair(S[u][i].Y,S[u][i].X));
sort(S[u].begin(),S[u].end());
LL last=1e15;
tmp.clear();
for (i=0;i<(int)S[u].size();i++)
if (last>S[u][i].Y) last=S[u][i].Y,tmp.push_back(S[u][i]);
S[u].clear();
for (i=0;i<(int)tmp.size();i++)
S[u].push_back(tmp[i]);
// printf("S[%d]:\n",u);
// for (i=0;i<(int)S[u].size();i++)
// printf("%lld %lld\n",S[u][i].X,S[u][i].Y);
// puts("");
}
bool pass()
{
// printf("<<<pass %lld>>>\n",mid);
int i;
for (i=1;i<=n;i++)
S[i].clear();
dfs(1);
// puts(""); puts(""); puts(""); puts(""); puts("");
return S[1].size();
}
int main()
{
#ifdef h10
freopen("E.in","r",stdin);
freopen("E.out","w",stdout);
#endif
int i;
LL L=0,R=0;
scanf("%d",&n);
for (i=2;i<=n;i++)
{
scanf("%d%d",&fa[i],&w[i]);
if (lc[fa[i]]) rc[fa[i]]=i;
else lc[fa[i]]=i;
R+=w[i];
}
while (L<=R)
{
mid=(L+R)>>1;
if (pass()) R=mid-1;
else L=mid+1;
}
printf("%lld\n",L);
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:69:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:72:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&fa[i],&w[i]);
^