记录编号	583632	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	删除题目	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.923 s
提交时间	2023-10-19 20:24:55	内存使用	12.72 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=100000+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n;
ll w[N];
vector<int>g[N];
struct line{
	ll k,b;
}li[N];
ll calc(int i,int x){
	return li[i].k*x+li[i].b;
}
struct segtree{
	int lc[4*N],rc[4*N],id[4*N],tot=0;
	void clear(){
		tot=0;memset(id,0,sizeof(id));
		memset(lc,0,sizeof(lc)),memset(rc,0,sizeof(rc));
		return ;
	}
	void insert(int &pt,int l,int r,int cur){
		if (!pt){id[pt=++tot]=cur;return ;}
		int mid=(l+r)/2;
		if (calc(id[pt],mid)<calc(cur,mid))swap(id[pt],cur);
		if (calc(id[pt],l)>=calc(cur,l)&&calc(id[pt],r)>=calc(cur,r))return ;
		if (calc(id[pt],l)<calc(cur,l))insert(lc[pt],l,mid,cur);
		else insert(rc[pt],mid+1,r,cur);
		return ;
	}
	ll query(int pt,int l,int r,int pos){
		if (!pt)return -inf;
		int mid=(l+r)/2;ll ans=calc(id[pt],pos);
		if (pos<=mid)ans=max(ans,query(lc[pt],l,mid,pos));
		else ans=max(ans,query(rc[pt],mid+1,r,pos));
		return ans;
	}
	int merge(int p1,int p2,int l,int r){
		if (!p1||!p2)return p1|p2;
		insert(p1,l,r,id[p2]);
		int mid=(l+r)/2;
		lc[p1]=merge(lc[p1],lc[p2],l,mid);
		rc[p1]=merge(rc[p1],rc[p2],mid+1,r);
		return p1;
	}
}T;
int rt[N];
int dfn[N],tim=0,S[N],wson[N],pos[N];
void prework(int pt){
	S[pt]=1;dfn[pt]=++tim;pos[tim]=pt;
	for (auto v:g[pt]){
		prework(v);S[pt]+=S[v];
		if (S[v]>S[wson[pt]])wson[pt]=v;
	}return ;
}
ll f[N],ans=0;
void solve1(int pt){
	for (auto v:g[pt]){
		solve1(v);
		rt[pt]=T.merge(rt[pt],rt[v],1,n);
	}
	if (pt==1)return ;
	ll cur=T.query(rt[pt],1,n,S[pt]);
	f[pt]=max(-w[pt],cur-w[pt]);
	li[pt]={S[pt],f[pt]-1ll*S[pt]*S[pt]};
	T.insert(rt[pt],1,n,pt);
	ans=max(ans,f[pt]+1ll*S[pt]*(n-S[pt]));
	return ;
}
void solve2(int pt){
	if (wson[pt])solve2(wson[pt]);
	for (auto v:g[pt]){
		if (v==wson[pt])continue;
		solve2(v);
		for (int i=dfn[v];i<=dfn[v]+S[v]-1;i++){
			int x=pos[i];
			ll cur=T.query(rt[wson[pt]],1,n,S[x]);
			ans=max(ans,cur+f[x]+1ll*S[x]*(n-S[x]));
		}
		rt[wson[pt]]=T.merge(rt[wson[pt]],rt[v],1,n);
	}
	if (pt==1)return ;
	rt[pt]=rt[wson[pt]];
	li[pt]={-S[pt],f[pt]-1ll*S[pt]*S[pt]+1ll*n*S[pt]};
	T.insert(rt[pt],1,n,pt);
	return ;
}
int main(){
	freopen ("delete.in","r",stdin);
	freopen ("delete.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n;i++){
		int p;scanf("%d%lld",&p,&w[i]);
		g[p].pb(i);
	}
	prework(1);
	solve1(1);
	T.clear(); 
	solve2(1);
	printf("%lld\n",ans);
	return 0;
}