比赛 4043级2023省选练习赛1 评测结果 AAAAAAAAAA
题目名称 树的果实 最终得分 100
用户昵称 yrtiop 运行时间 0.659 s
代码语言 C++ 内存使用 11.52 MiB
提交时间 2023-03-03 19:41:09
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 1e5 + 5;
int n,a[maxn],c[maxn],cnt,buc[maxn],res[maxn],sum[maxn];
std::vector<int> G[maxn];

struct BIT {
	int c[maxn];
	int lowbit(int x) {
		return x & -x;
	}
	void add(int x,int y) {
		for(;x <= cnt;x += lowbit(x))
			c[x] += y;
		return ;
	}
	int query(int x) {
		int ans = 0;
		for(;x;x -= lowbit(x))
			ans += c[x];
		return ans;
	}
} tr1,tr2;

void dfs(int u) {
	tr1.add(a[u] , 1);
	tr2.add(a[u] , 1);
	sum[u] = tr1.query(cnt) - tr1.query(a[u]);
	res[u] = tr2.query(cnt) - tr2.query(a[u]);
	for(auto& v : G[u])
		dfs(v);
	sum[u] = tr1.query(cnt) - tr1.query(a[u]) - sum[u];
	tr2.add(a[u] , -1);
	return ;
}

int main() {
	freopen("treesfruits.in","r",stdin);
	freopen("treesfruits.out","w",stdout);
	scanf("%d",&n);
	for(int x,i = 2;i <= n;++ i)
		scanf("%d",&x),G[x].pb(i);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i]),c[++ cnt] = a[i];
	std::sort(c + 1 , c + 1 + cnt);
	cnt = std::unique(c + 1 , c + 1 + cnt) - c - 1;
	for(int i = 1;i <= n;++ i)
		a[i] = std::lower_bound(c + 1 , c + 1 + cnt , a[i]) - c,++ buc[a[i]];
	for(int i = cnt;i;-- i)
		buc[i] += buc[i + 1];
	dfs(1);
	for(int i = 1;i <= n;++ i)
		printf("%d %d %d\n",sum[i],buc[a[i] + 1] - sum[i],res[i]);
	return 0;
}