记录编号	460857	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2004] 树的果实	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	9.280 s
提交时间	2017-10-18 17:47:21	内存使用	5.65 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e;
	edge *n;
}*pre[100005];
inline void insert(int s,int e){
	edge *tmp(new edge);
	tmp->e=e;tmp->n=pre[s];pre[s]=tmp;
}
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int key,fix,size;
	node(int x=0):lch(NULL),rch(NULL),size(1),fix(rand()),key(x){}
	inline void pushup(){this->size=get_size(this->lch)+get_size(this->rch)+1;}
}*tr[400005];
inline void left_rotate(node *&x){
	node *tmp(x->rch);
	x->rch=tmp->lch;
	tmp->lch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void right_rotate(node *&x){
	node *tmp(x->lch);
	x->lch=tmp->rch;
	tmp->rch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void insert(node *&x,int v){
	if(!x){
		x=new node(v);
		return;
	}
	if(v<=x->key){
		insert(x->lch,v);
		x->pushup();
		if(x->lch->fix<x->fix)
			right_rotate(x);
	}
	else{
		insert(x->rch,v);
		x->pushup();
		if(x->rch->fix<x->fix)
			left_rotate(x);
	}
}
inline int qmax(node *now,int x){
	int ret(0);
	while(now){
		if(x>=now->key)now=now->rch;
		else ret+=get_size(now->rch)+1,now=now->lch;
	}
	return ret;
}
int n;
int w[100005];
int fa[100005],son[100005],size[100005],dep[100005];
inline void dfs1(int u){
	size[u]=1;son[u]=0;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);
		if(e==fa[u])continue;
		fa[e]=u;
		dep[e]=dep[u]+1;
		dfs1(e);
		size[u]+=size[e];
		if(size[e]>size[son[u]])son[u]=e;
	}
}
int cnt;
int l[100005],r[100005],pos[100005],top[100005];
inline void dfs2(int u,int rt){
	top[u]=rt;
	l[u]=++cnt;
	pos[cnt]=u;
	if(son[u])dfs2(son[u],rt);
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);
		if(e==fa[u]||e==son[u])continue;
		dfs2(e,e);
	}
	r[u]=cnt;
}
inline void build(int l,int r,int rt){
	for(int i=l;i<=r;++i)insert(tr[rt],w[pos[i]]);
	if(l==r)return;
	int mid((l+r)>>1);
	build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
}
inline int qmax(int ll,int rr,int x,int l,int r,int i){
	if(ll<=l&&r<=rr)return qmax(tr[i],x);
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)ret+=qmax(ll,rr,x,l,mid,i<<1);
	if(mid<rr)ret+=qmax(ll,rr,x,mid+1,r,i<<1|1);
	return ret;
}
inline int query(int x,int y,int w){
	int ret(0);
	while(top[x]^top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ret+=qmax(l[top[x]],l[x],w,1,n,1);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ret+=qmax(l[x],l[y],w,1,n,1);
	return ret;
}
int main(){
	freopen("treesfruits.in","r",stdin);
	freopen("treesfruits.out","w",stdout);
	n=read();
	for(int i=2;i<=n;++i){
		int x(read());
		insert(x,i);
	}
	for(int i=1;i<=n;++i)w[i]=read();
	dfs1(1);dfs2(1,1);
	build(1,n,1);
	for(int i=1;i<=n;++i)printf("%d %d %d\n",qmax(l[i],r[i],w[i],1,n,1),i==1?0:(qmax(1,l[i]-1,w[i],1,n,1)+qmax(r[i]+1,n,w[i],1,n,1)),query(1,i,w[i]));
}