提交记录

Code：

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <cstdio>
#define ll long long
#define P pair<int, int>
#define MP make_pair
#define PU push_back
#define li(x) x << 1
#define ri(x) (x << 1) | 1
#define LLF LLONG_MAX >> 2
#define INF INT_MAX >> 1
using namespace std;
const int N = 3e5 + 5;
int n, m, tot, head[N], trip[N], dep[N], fa[N][25], cha[N];

struct Edge{
	int u, v, w, nex;
}e[N << 1];

inline ll read(){
	ll f = 1, x = 0;
	char c = getchar();
	while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
	while('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (ll)(c - '0'), c = getchar();
	return x * f;
}

inline void write(ll x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void add(int u, int v){
	e[++tot] = {u, v, 1, head[u]};
	head[u] = tot;
}

void DFS(int u, int fr){
	dep[u] = dep[fr] + 1;
	fa[u][0] = fr;
	for(int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(int i = head[u]; i; i = e[i].nex){
		int v = e[i].v;
		if(v != fr) DFS(v, u);
	}
}

inline int LCA(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 20; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
	if(x == y) return x;
	for(int i = 20; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

void get_answer(int u, int fr){
	for(int i = head[u]; i; i = e[i].nex){
		int v = e[i].v;
		if(v == fr) continue;
		DFS(v, u);
		cha[u] += cha[v];
	}
}

int main(){
//	freopen("water.in.txt", "r", stdin);
//	freopen("water.out.txt", "w", stdout);

//  ios::sync_with_stdio(false);
//  cin.tie(0), cout.tie(0);
	
	n = read();
	for(int i = 1; i <= n; i++) trip[i] = read();
	for(int i = 1, u, v; i < n; i++){
		u = read(), v = read();
		add(u, v);
		add(v, u);
	}
	DFS(1, 0);
	for(int i = 1; i < n; i++){
		int u = trip[i], v = trip[i + 1];
		int lca = LCA(u, v);
		cha[u]++, cha[v]++, cha[lca]--, cha[fa[lca][0]]--;
	}
	get_answer(1, 0);
	for(int i = 2; i <= n; i++) cha[trip[i]]--;
	for(int i = 1; i <= n; i++) write(cha[i]), putchar('\n');
	return 0;
}