和三角形没有关系
只要知道儿子放置的顺序，就可以直接模拟了
记录历史最大值
用一个pair(a,b)：之后加上a个，期间最大值为增加b个
合并？
A1+A2=(a1+a2,max(b1,a1+b2))
放置顺序考虑贪心
比较：
A放在B前面（和父亲进行合并）当且仅当(C=A+B).b<(D=B+A).b
分A.a和B.a的正负进行讨论
初始的pair：（w[x]-∑w[son[x]],w[x]）把儿子会都扔掉
初始的pair放进堆里，取n-1次，和父亲合并，加入新的连通块的pair
链表维护操作序列
处理出操作顺序，模拟或者线段树合并
懒惰删除堆自带的bug
必须要使得决策堆和删除堆的元素的相对顺序是一样的！
小于号重载充分！不能出现决策堆A,B,删除堆B,A的情况！
小于号重载充分的话：
使得除非二者完全相等，否则必须有固定的大小顺序（未定义的话会有很多相等，比较就是随机的）
这样才能使得两个堆的相对位置相同。
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{
const int N=2e5+;
int n;
struct po{
ll a,b;
int id;
po(){}
po(ll aa,ll bb,ll dd){
a=aa;b=bb;id=dd;
}
po friend operator +(po a,po b){
return po(a.a+b.a,max(a.b,a.a+b.b),b.id);//warning!!! b.id
}
bool friend operator <(po a,po b){
// if(a.a==b.a&&a.b==b.b) return a.id<b.id;
if(a.a<=&&b.a>) return ;
if(a.a>&&b.a<=) return ;
if(a.a<=&&b.a<=){
if(a.b!=b.b) return a.b<b.b;
if(a.id!=b.id) a.id>b.id;
return a.a<b.a;
}
if(a.a-a.b!=b.a-b.b) return a.a-a.b<b.a-b.b;
if(a.id!=b.id) return a.id>b.id;
return a.a>b.a;
}
bool friend operator ==(po a,po b){
return (a.a==b.a)&&(a.b==b.b)&&(a.id==b.id);
}
void op(){
cout<<a<<" "<<b<<" : "<<id<<endl;
}
}nc[N],ori[N]; priority_queue<po>q,d; int ff[N];
int fin(int x){
return ff[x]==x?x:ff[x]=fin(ff[x]);
}
int st[N],nd[N];
struct lc{
int pre,nxt,id;
}p[N];
int pos[N];
struct node{
int ls,rs;
po ans;
}t[*N];
int tot;
int rt[N];
int vis[N];
void pushup(int x){
t[x].ans=t[t[x].ls].ans+t[t[x].rs].ans;
}
void upda(int &x,int l,int r,int p,po c){
x=++tot;
if(l==r){t[x].ans=c;return;}
if(p<=mid) upda(t[x].ls,l,mid,p,c);
else upda(t[x].rs,mid+,r,p,c);
pushup(x);
}
int merge(int x,int y){
if(!x||!y) return x+y;
t[x].ls=merge(t[x].ls,t[y].ls);
t[x].rs=merge(t[x].rs,t[y].rs);
pushup(x);
return x;
}
int pa[N],w[N];
ll ans[N];
int main(){
int haha;rd(haha);
rd(n);
for(reg i=;i<=n;++i) rd(pa[i]);
for(reg i=;i<=n;++i) {
rd(w[i]);ff[i]=i;
nc[i].id=i;
nc[i].a+=w[i];nc[i].b=w[i];
nc[pa[i]].a-=w[i];
p[i].pre=p[i].nxt=;
p[i].id=i;
st[i]=nd[i]=i;
}
for(reg i=;i<=n;++i) {
ori[i]=nc[i];
if(i!=)q.push(nc[i]);
}
int o=n-;
while(o--){
po now=q.top();q.pop();
// cout<<now.a<<" "<<now.b<<" "<<now.id<<endl;
if(now.id==){
cout<<" shit ";return ;
}
if(vis[now.id]){
cout<<" mmp "<<now.id<<" eqaul "<<(now==ori[now.id]);return ;
}
vis[now.id]=; int to=fin(pa[now.id]);
// cout<<" to "<<to<<endl;
ff[now.id]=to;
if(to!=){
d.push(nc[to]);
// cout<<" dele "<<endl;
// nc[to].op();
nc[to]=now+nc[to];
// nc[to].op();
// cout<<" over "<<endl;
q.push(nc[to]);
}
p[nd[now.id]].nxt=st[to];
p[st[to]].pre=nd[now.id];
st[to]=st[now.id]; while(q.size()&&d.size()) {
// po lp1=d.top(),lp2=q.top();
// cout<<" rubish "<<endl;
// lp2.op();lp1.op();
if(!(q.top()==d.top())) break;
q.pop(),d.pop();
}
}
for(reg i=;i<=n;++i){
if(!vis[i]){
cout<<" WTF "<<i;return ;
}
} int x=st[];
for(reg i=;i<=n;++i){
pos[x]=i;
x=p[x].nxt;
}
// prt(pos,1,n);
for(reg i=;i<=n;++i){
upda(rt[i],,n,pos[i],ori[i]);
}
// prt(rt,1,n); x=st[];
for(reg i=;i<=n;++i){
ans[x]=t[rt[x]].ans.b;
if(pa[x]){
rt[pa[x]]=merge(rt[pa[x]],rt[x]);
}
x=p[x].nxt;
}
prt(ans,,n);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/4/13 19:58:12
*/