和三角形没有关系
只要知道儿子放置的顺序，就可以直接模拟了
记录历史最大值
用一个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=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) 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(' ');} namespace Miracle{ const int N=2e5+5; 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<=0&&b.a>0) return 1; if(a.a>0&&b.a<=0) return 0; if(a.a<=0&&b.a<=0){ 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[40*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+1,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=2;i<=n;++i) rd(pa[i]); for(reg i=1;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=0; p[i].id=i; st[i]=nd[i]=i; } for(reg i=1;i<=n;++i) { ori[i]=nc[i]; if(i!=1)q.push(nc[i]); } int o=n-1; while(o--){ po now=q.top();q.pop(); // cout<<now.a<<" "<<now.b<<" "<<now.id<<endl; if(now.id==1){ cout<<" shit ";return 0; } if(vis[now.id]){ cout<<" mmp "<<now.id<<" eqaul "<<(now==ori[now.id]);return 0; } vis[now.id]=1; int to=fin(pa[now.id]); // cout<<" to "<<to<<endl; ff[now.id]=to; if(to!=1){ 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=2;i<=n;++i){ if(!vis[i]){ cout<<" WTF "<<i;return 0; } } int x=st[1]; for(reg i=1;i<=n;++i){ pos[x]=i; x=p[x].nxt; } // prt(pos,1,n); for(reg i=1;i<=n;++i){ upda(rt[i],1,n,pos[i],ori[i]); } // prt(rt,1,n); x=st[1]; for(reg i=1;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,1,n); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/4/13 19:58:12 */