Submission #74771554

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

namespace io{const int __SIZE=(1<<21)+1;char ibuf[__SIZE],*iS,*iT,obuf[__SIZE],*oS=obuf,*oT=oS+__SIZE-1,__c,qu[55];int __f,qr,_eof;
#define Gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,__SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}inline void gc(char&x){x=Gc();}inline void pc(char x){*oS++=x;if(oS==oT)flush();}inline void pstr(const char*s){int __len=strlen(s);for(__f=0;__f<__len;++__f)pc(s[__f]);}inline void gstr(char*s){for(__c=Gc();__c<32||__c>126||__c==' ';)__c=Gc();for(;__c>31&&__c<127&&__c!=' '&&__c!='\n'&&__c!='\r';++s,__c=Gc())*s=__c;*s=0;}template<class I>inline bool gi(I&x){_eof=0;for(__f=1,__c=Gc();(__c<'0'||__c>'9')&&!_eof;__c=Gc()){if(__c=='-')__f=-1;_eof|=__c==EOF;}for(x=0;__c<='9'&&__c>='0'&&!_eof;__c=Gc())x=x*10+(__c&15),_eof|=__c==EOF;x*=__f;return!_eof;}template<class I>inline void print(I x){if(!x)pc('0');if(x<0)pc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)pc(qu[qr--]);}struct Flusher_{~Flusher_(){flush();}}io_flusher_;}using io::pc;using io::gc;using io::pstr;using io::gstr;using io::gi;using io::print;

constexpr int N=200010,INF=0x3f3f3f3f3f3f3f3f;
int n,fa[N],w[N],sz[N];
vector<int> son[N];
int ans=0;

void dfs(int x){
	if(son[x].size()==0){
		sz[x]=w[x];
		return;
	}
	int mn=INF,mx=-INF;
	for(int y:son[x]){
		dfs(y);
		mn=min(mn,sz[y]);
		mx=max(mx,sz[y]);
		sz[x]+=sz[y];
	}
	ans=max(ans,mx-mn);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		son[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	dfs(1);
	cout<<ans;
	return 0;
}

Submission Info

Judge Result