记录编号	586576	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2004] 树的果实	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.698 s
提交时间	2024-02-07 23:16:17	内存使用	20.53 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m;
struct node{
	int id,p;
	bool operator < (const node x)const{//这里不加const会编译错误 
		return p < x.p;
	}
}a[N];
struct BIT{
	int c[N];
	int lowbit(int x){return (x & (-x));}
	void clear(){memset(c,0,sizeof c);}
	void add(int x,int z){
		for(;x <= n;x += lowbit(x))c[x] += z;
	}
	ll ask(int x){
		ll ans = 0;
		for(;x > 0;x -= lowbit(x))ans += c[x];
		return ans;
	}
}t;
struct made{
	int ver,nx;
}e[N<<1];
int hd[N],tot,cnt;
int dfn[N],siz[N],c[N],p[N];
ll A[N],B[N],C[N]; 
void add(int x,int y){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs(int x){
	siz[x] = 1,dfn[x] = ++cnt;
	C[x] = t.ask(a[x].p-1);
	t.add(a[x].p,1);
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		dfs(y);
		siz[x] += siz[y];
	}
	t.add(a[x].p,-1);
}
void work(){
	sort(a+1,a+1+n);
	t.clear();
	for(int i = 1;i <= n;){
		int j = i;
		while(a[i].p == a[j].p){
			int x = a[i].id;
			A[x] = t.ask(dfn[x]+siz[x]-1) - t.ask(dfn[x]);
			B[x] = t.ask(n) - A[x]; 
			j++; 
		}
		while(i < j)t.add(dfn[a[i].id],1),i++;
	}
}
int main(){
	freopen("treesfruits.in","r",stdin);
	freopen("treesfruits.out","w",stdout);
	scanf("%d",&n);
	for(int i = 2;i <= n;i++){
		int x;scanf("%d",&x);
		add(x,i);
	}
	for(int i = 1;i <= n;i++)scanf("%d",&p[i]),c[i] = p[i];
	sort(c+1,c+1+n);
	m = unique(c+1,c+1+n) - (c+1);
	for(int i = 1;i <= n;i++){
		a[i].id = i;
		a[i].p = lower_bound(c+1,c+1+m,p[i]) - c;
		a[i].p = m + 1 - a[i].p;//把后缀和改为树状数组的前缀和 
	}
	t.clear();
	dfs(1);
	work();
	for(int i = 1;i <= n;i++)printf("%lld %lld %lld\n",A[i],B[i],C[i]);
	
	return 0;
	
}