算法分析
可以用树上 $\operatorname{dfs}$ 来统计区间 $\bigg[\operatorname{in}[1], \operatorname{out}[v]\bigg]$ 中每个点对 点 $v$ 上点权 $p$ 的贡献,然后将它容斥掉区间 $\bigg[\operatorname{in}[1], \operatorname{in}[v]\bigg]$ 中的点对点权 $p$ 的贡献,就能求出点 $v$ 的答案。
其中的贡献可以用树状数组来维护
注意,需要做离散化!
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
template<typename T>
struct BIT {
int n;
vector<T> d;
BIT(int n=0):n(n),d(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
d[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += d[i];
}
return x;
}
T sum(int l, int r) {
return sum(r-1) - sum(l-1);
}
};
// Coodinate Compression
template<typename T=int>
struct CC {
bool initialized;
vector<T> xs;
CC(): initialized(false) {}
void add(T x) { xs.push_back(x);}
void init() {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
initialized = true;
}
int operator()(T x) {
if (!initialized) init();
return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
}
T operator[](int i) {
if (!initialized) init();
return xs[i];
}
int size() {
if (!initialized) init();
return xs.size();
}
};
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
CC cc;
rep(i, n) cc.add(a[i]);
vector<vector<int>> to(n);
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
--p;
to[p].push_back(i);
}
vector<int> ans(n);
BIT<int> t(n);
auto dfs = [&](auto f, int v) -> void {
ans[v] = t.sum(cc(a[v])+1, n);
for (int u : to[v]) {
f(f, u);
}
ans[v] = t.sum(cc(a[v])+1, n) - ans[v];
t.add(cc(a[v]));
};
dfs(dfs, 0);
rep(i, n) cout << ans[i] << '\n';
return 0;
}