Submission #1690663

---

Source Code Expand

/*
神题
二分答案+分析性质
合并集合优化DP，满二叉树-->O(n*logn)
O(n*logn*logw)
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 131110
#define ll long long
#define top 1000000000000LL
#define pa(a, b) (data){a, b}
using namespace std;

struct data{ll in, out;};
int n, sum[N], son[N][2], w[N], x, y;
ll L, R, mid;
vector<data>s[N], s1, s2;

inline char gc(){
	return getchar();
	static char now[1<<16], *S, *T;
	if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;}
	return *S++;
}
inline int read(){
	int x=0, f=1; char ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=gc();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=gc();}
	return x*f;
}

inline void dp(int x, ll L){
	if(!sum[x]){s[x].push_back(pa(0, 0)); return;}
	int l=son[x][0], r=son[x][1];
	dp(l, L); dp(r, L);
	s[x].clear(); s1.clear(); s2.clear();
	int now=-1, now1=-1;
	for(int i=0; i<s[l].size(); i++){
		while(now+1<s[r].size()&&s[l][i].out+w[l]+w[r]+s[r][now+1].in<=L)now++;
		if(now==now1)continue;
		s1.push_back(pa(s[l][i].in+w[l], w[r]+s[r][now].out));
		now1=now;
	}
	now=now1=-1;
	for(int i=0; i<s[r].size(); i++){
		while(now+1<s[l].size()&&s[r][i].out+w[r]+w[l]+s[l][now+1].in<=L)now++;
		if(now==now1)continue;
		s2.push_back(pa(s[r][i].in+w[r], w[l]+s[l][now].out));
		now1=now;
	}
	int p1=0, p2=0;
	while(p1<s1.size()&&p2<s2.size()){
		if(s1[p1].in<s2[p2].in){s[x].push_back(s1[p1]); p1++;}
		else if(s1[p1].in>s2[p2].in){s[x].push_back(s2[p2]); p2++;}
		else{s[x].push_back(pa(s1[p1].in, min(s1[p1].out, s2[p2].out))); p1++; p2++;}
	}
	while(p1<s1.size()){s[x].push_back(s1[p1]); p1++;}
	while(p2<s2.size()){s[x].push_back(s2[p2]); p2++;}
}

inline int check(ll L){
	dp(1, L);
	return s[1].size()?1:0;
}

int main(){
	n=read();
	memset(sum, 0, sizeof(sum));
	for(int i=2; i<=n; i++){
		x=read(); w[i]=read();
		sum[x]++; son[x][sum[x]-1]=i;
	}
	L=0; R=top;
	while(L<R){
		mid=(L+R)>>1;
		if(check(mid))R=mid; else L=mid+1;
	}
	printf("%lld", L);
	return 0;
}

Submission Info

Judge Result