记录编号	593450	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	删除题目	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.967 s
提交时间	2024-09-02 19:03:23	内存使用	80.45 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e5+10;
const ll inf = 1e18;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n;
ll w[N];


struct line{
	ll k,b = -inf;
	line(ll k,ll b):k(k),b(b){}
	line(){}
	ll val(ll x){return k * x + b;}
};
bool cmp(line a,line b,ll x){return a.val(x) > b.val(x);}

int root[N];
struct LiChao_tree{
	line mx[N<<5];int ls[N<<5],rs[N<<5],cnt;
	void clear(){
		cnt = 0;
		memset(root,0,sizeof root);
		for(int i = 0;i <= 32 * n;i++)mx[i] = {0,-inf},ls[i] = rs[i] = 0;
	}
	line ask(line a,line b,ll x){return cmp(a,b,x) ? a : b;}
	void modify(int &p,int l,int r,line x){
		if(l > r)return;
		if(!p)return mx[p = ++cnt] = x,void();
		int mid = l + r >> 1;
		if(cmp(x,mx[p],mid))swap(x,mx[p]);
		if(cmp(x,mx[p],l))modify(ls[p],l,mid,x);
		if(cmp(x,mx[p],r))modify(rs[p],mid+1,r,x);
	}
	line cal(int p,int l,int r,ll x){
		if(!p)return {0,-inf};
		if(l == r)return mx[p];
		int mid = l + r >> 1;
		if(x <= mid)return ask(cal(ls[p],l,mid,x),mx[p],x);
		else return ask(cal(rs[p],mid+1,r,x),mx[p],x);
	}
	int merge(int p,int q,int l,int r){
		if(!p || !q)return p | q;
		modify(p,l,r,mx[q]);
		int mid = l + r >> 1;
		ls[p] = merge(ls[p],ls[q],l,mid),rs[p] = merge(rs[p],rs[q],mid+1,r);
		return p;
	}
}t;


ll f[N],ans;
vector<int>e[N];
struct Tree{
	int dfn[N],rnk[N],son[N],cnt;
	ll siz[N];
	void dfs1(int x){
		dfn[x] = ++cnt,rnk[cnt] = x,siz[x] = 1;
		for(int y : e[x]){
			dfs1(y),siz[x] += siz[y];
			if(!son[x] || siz[y] > siz[son[x]])son[x] = y;
		}
	}
	void dp(int x){
		for(int y : e[x]){
			dp(y);
			root[x] = t.merge(root[x],root[y],1,n);
		}
		f[x] = max(-w[x],t.cal(root[x],1,n,siz[x]).val(siz[x]) - w[x]);
		t.modify(root[x],1,n,{siz[x],f[x] - siz[x] * siz[x]});
		ans = max(ans,f[x] + siz[x] * (n - siz[x]));
	}
	void dfs2(int x){
		for(int y : e[x]){
			if(y == son[x])continue;
			dfs2(y);
		}
		if(son[x])dfs2(son[x]);
		for(int y : e[x]){
			if(y == son[x])continue;
			for(int i = dfn[y];i < dfn[y] + siz[y];i++){
				int now = rnk[i];
				ll val = t.cal(root[son[x]],1,n,siz[now]).val(siz[now]);
				ans = max(ans,f[now] + siz[now] * (n - siz[now]) + val);
			}
			root[son[x]] = t.merge(root[son[x]],root[y],1,n);
		}
		root[x] = root[son[x]];
		t.modify(root[x],1,n,{-siz[x],f[x] + siz[x] * (n - siz[x])});
	}
}T;


int main(){
	freopen("delete.in","r",stdin);
	freopen("delete.out","w",stdout);
	n = read();
	for(int i = 2;i <= n;i++){
		int x = read();w[i] = read();
		e[x].pb(i);
	}
	T.dfs1(1),T.dp(1);
	t.clear(),T.dfs2(1);
	printf("%lld\n",ans);

	return 0;

}