C++11(clang++ 3.9) 解法, 执行用时: 2140ms, 内存消耗: 131204K, 提交时间: 2019-01-10 20:52:05

#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
	register char ch;
	register bool neg=false;
	while(!isdigit(ch=getchar())) neg|=ch=='-';
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return neg?-x:x;
}
const int N=2e6+1;
std::vector<int> e[N];
int w[N],ans,max[N][2],min[N][2];
inline void add_edge(const int &u,const int &v) {
	e[u].push_back(v);
	e[v].push_back(u);
}
inline void upd1(const int &x,const int &y) {
	int tmp1=min[y][0]+w[x];
	int tmp2=max[y][0]+w[x];
	for(register int i=0;i<2;i++) {
		if(tmp1<min[x][i]) {
			std::swap(tmp1,min[x][i]);
		}
		if(tmp2>max[x][i]) {
			std::swap(tmp2,max[x][i]);
		}
	}
}
inline void upd2(const int &x,const int &y) {
	int tmp1=min[y][min[y][0]==min[x][0]+w[y]];
	int tmp2=max[y][max[y][0]==max[x][0]+w[y]];
	if(tmp1!=INT_MAX) tmp1+=w[x];
	if(tmp2!=INT_MIN) tmp2+=w[x];
	for(register int i=0;i<2;i++) {
		if(tmp1!=INT_MAX&&tmp1<min[x][i]) {
			std::swap(tmp1,min[x][i]);
		}
		if(tmp2!=INT_MIN&&tmp2>max[x][i]) {
			std::swap(tmp2,max[x][i]);
		}
	}
}
void dfs1(const int &x,const int &par) {
	max[x][0]=min[x][0]=w[x];
	max[x][1]=INT_MIN;
	min[x][1]=INT_MAX;
	for(auto &y:e[x]) {
		if(y==par) continue;
		dfs1(y,x);
		upd1(x,y);
	}
}
void dfs2(const int &x,const int &par) {
	for(auto &y:e[x]) {
		if(y==par) continue;
		ans=std::max(ans,std::min(std::abs(max[y][0]),std::abs(min[x][min[x][0]==min[y][0]+w[x]])));
		ans=std::max(ans,std::min(std::abs(min[y][0]),std::abs(max[x][max[x][0]==max[y][0]+w[x]])));
		upd2(y,x);
		dfs2(y,x);
	}
}
int main() {
	int n;
	while(~scanf("%d",&n)) {
		for(register int i=1;i<=n;i++) {
			const int p=getint();
			if(p) add_edge(p,i);
			w[i]=getint();
		}
		dfs1(1,0);
		dfs2(1,0);
		printf("%d\n",ans);
		for(register int i=1;i<=n;i++) {
			e[i].clear();
		}
		ans=0;
	}
	return 0;
}