算法
(树上差分、LCA) $O(N\log N)$
本题是树上差分板题
把 $a[i]\longleftrightarrow a[i+1]$ 看作树上的一条链,然后做树上差分即可
注意到除了 $a[1]$ 和 $a[n]$以外,其他点都被添加了两次 +1
的记号,此外,题中说 $a[n]$ 不需要考虑,所以要对除去 $a[1]$ 以外的所有点添加 -1
的记号
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int MX = 300005;
int anc[MX][20], dep[MX], d[MX], a[MX];
vector<int> to[MX];
void dfs(int v, int p=0) {
for (int u : to[v]) {
if (u == p) continue;
anc[u][0] = v;
dep[u] = dep[v] + 1;
dfs(u, v);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
int d = dep[x] - dep[y];
rep(i, 20) {
if (d>>i & 1) x = anc[x][i];
}
if (x == y) return x;
for (int i = 19; i >= 0; --i) {
if (anc[x][i] != anc[y][i]) {
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
void dfs2(int v, int p=0) {
for (int u : to[v]) {
if (u == p) continue;
dfs2(u, v);
d[v] += d[u];
}
}
int main() {
int n;
cin >> n;
rep(i, n) cin >> a[i];
rep(i, n-1) {
int u, v;
cin >> u >> v;
to[u].push_back(v);
to[v].push_back(u);
}
dfs(1);
for (int i = 1; i < 20; ++i) {
for (int j = 1; j <= n; ++j) {
anc[j][i] = anc[anc[j][i-1]][i-1];
}
}
rep(i, n-1) {
int u = a[i], v = a[i+1];
d[u]++;
d[v]++;
d[anc[lca(u, v)][0]]--;
d[lca(u, v)]--;
}
dfs2(1);
for (int i = 1; i < n; ++i) d[a[i]]--;
for (int i = 1; i <= n; ++i) {
cout << d[i] << '\n';
}
return 0;
}