Submission #1839723

---

Source Code Expand

#include<bits/stdc++.h>
#define N ((1<<17)+3)
using namespace std;
vector<int> son[N];
vector<pair<int,long long> > dp[N];
long long mid,dis[N];
vector<pair<int,long long> > temp;
bool DFS(int u,int fr){
    dp[u].clear();
    for(int i:son[u]) 
        if(!DFS(i,u))
            return false;
    if(son[u].size()==0){
        dp[u].push_back(make_pair(0,0));
    }else{
        temp.clear();
        int l=son[u][0],r=son[u][1],limit=mid-dis[l]-dis[r];
        if(dp[l].size()>dp[r].size()) swap(l,r);
        for(int i=0,p=0;i<dp[l].size()&&p<dp[r].size();i++){
            while(p+1<dp[r].size() && dp[l][i].second+dp[r][p+1].first <= limit) p++;
            if(dp[l][i].second+dp[r][p].first <= limit) 
                temp.push_back(make_pair( dp[l][i].first+dis[l],dp[r][p].second+dis[r] ));
        }
        for(int i=temp.size()-1;i>=0;i--) 
            temp.push_back(make_pair(temp[i].second,temp[i].first));
        sort(temp.begin(),temp.end());
        for(pair<int,int> x:temp){
            if(dp[u].size()==0|| x.second < dp[u][dp[u].size()-1].second )
                dp[u].push_back(x);
        }
    }
    return dp[u].size()!=0;
}

int n,fa[N];

int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d%lld",&fa[i],&dis[i]),son[fa[i]].push_back(i);
    long long l=-1,r=2e9;//(]
    while(l+1<r){
        mid=(l+r)>>1;
        if(!DFS(1,0)) l=mid;
        else r=mid;
    }
    cout<<r<<endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:39:81: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for(int i=2;i<=n;i++) scanf("%d%lld",&fa[i],&dis[i]),son[fa[i]].push_back(i);
                                                                                 ^

Judge Result