代码如下,请各位 dalao 来康康本蒟蒻的代码哪里错了:
#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, a[N];
int pre[N][22], deep[N], d[N], fa[N];
int tot, head[N];
struct node{
int to, next;
}edges[2 * N];
void add(int u, int v){
tot++;
edges[tot].to = v;
edges[tot].next = head[u];
head[u] = tot;
}
void dfs(int x){
for(int i = head[x]; i; i = edges[i].next){
if(edges[i].to == fa[x]){
continue;
}
dfs(edges[i].to);
d[x] += d[edges[i].to];
}
}
struct LCA{
void dfs(int x, int f){
fa[x] = f;
pre[x][0] = f;
for(int i = 1; i <= 21; i++){
pre[x][i] = pre[pre[x][i - 1]][i - 1];
}
for(int i = head[x]; i; i = edges[i].next){
if(edges[i].to == f){
continue;
}
deep[edges[i].to] = deep[x] + 1;
dfs(edges[i].to, x);
}
}
int lca(int x, int y){
if(deep[x] > deep[y]){
swap(x, y);
}
for(int i = 21; i >= 0; i--){
if(deep[pre[y][i]] >= deep[x]){
y = pre[y][i];
}
}
if(x == y){
return x;
}
for(int i = 21; i >= 0; i--){
if(pre[y][i] != pre[x][i]){
x = pre[x][i];
y = pre[y][i];
}
}
return pre[x][0];
}
}l;
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
l.dfs(1, 0);
for(int i = 1; i < n; i++){
int lca = l.lca(a[i], a[i + 1]);
d[a[i]]++;
d[a[i + 1]]++;
d[lca]--;
d[fa[lca]]--;
}
dfs(1);
for(int i = 2; i <= n; i++){
d[a[i]]--;
}
for(int i = 1; i <= n; i++){
cout << d[i] << endl;
}
return 0;
}