比赛 |
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;
}