Submission #1819881

---

Source Code Expand

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 2333333333333333333LL
 
struct edge { int t,v,next; }a[400010];
 
struct node
{
    ll a,b;
    node() {}
    node(ll a,ll b):a(a),b(b) {}
}p[200010],q[200010];
 
vector<node> v[200010];
 
int head[200010],f[200010],in[200010],n,t1,t2,tot;
ll h[200010],mx,ans;
 
inline int rd()
{
    int x=0;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}
 
inline void add(int x,int y,int z) { a[++tot].t=y;a[tot].v=z;a[tot].next=head[x];head[x]=tot; }
 
inline void dfs(int x,int y)
{
    if (in[x]==1) { v[x].push_back(node(0,0));return; }
    int h1=0,h2=0,s1,s2,i1,i2;
    for (int i=head[x];i;i=a[i].next)
    {
        int t=a[i].t;
        if (t==y) continue;
        f[t]=a[i].v;dfs(t,x);
        if (!h1) h1=t;
        else h2=t;
    }
    s1=v[h1].size();s2=v[h2].size();
    if (!s1||!s2) return;
    if (s1>s2) swap(s1,s2),swap(h1,h2);
    ll hh=mx-f[h1]-f[h2],minn=inf;
    t1=t2=i2=0;
    for (i1=0;i1<s1;i1++)
    {
        while (v[h1][i1].b+minn>hh&&i2<s2) minn=min(minn,v[h2][i2++].a);
        if (v[h1][i1].b+minn>hh) break;
        p[++t1]=(node){v[h1][i1].a+f[h1],v[h2][i2-1].b+f[h2]};
    }
    for (int i=0;i<s1;i++) h[i]=inf;
    minn=inf;i1=0;
    for (i2=0;i2<s2;i2++)
    {
        while (v[h2][i2].b+minn>hh&&i1<s1) minn=min(minn,v[h1][i1++].a);
        if (v[h2][i2].b+minn>hh) break;
        h[i1-1]=min(h[i1-1],v[h2][i2].a+f[h2]);
    }
    for (int i=0;i<s1;i++) if (h[i]!=inf) q[++t2]=(node){h[i],v[h1][i].b+f[h1]};
    i1=1;i2=1;
    while (i1<=t1||i2<=t2)
    {
        node hh;
        if (i2>t2) hh=p[i1++];
        else if (i1>t1||p[i1].b>q[i2].b) hh=q[i2++];
        else hh=p[i1++];
        v[x].push_back(hh);
    }
}
 
inline bool check()
{
    for (int i=1;i<=n;i++) v[i].clear();
    dfs(1,0);
    if (v[1].size()) return true;
    return false;
}
 
int main()
{
    n=rd();
    for (int i=2;i<=n;i++)
    {
       int x=rd(),y=rd();
       add(i,x,y);add(x,i,y);
       in[i]++;in[x]++;
    }
    ll l=0,r=233333333333LL;
    while (l<r)
    {
       mx=(l+r)>>1;
       if (check()) r=mx;
       else l=mx+1;
    }
    printf("%lld\n",l);
    return 0;
}

Submission Info

Judge Result