1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#include <bits/stdc++.h>
using namespace std;

// brute.cpp：逐条路径 BFS 找父亲并枚举路径点，只适合小数据。

const int MAXN = 505;

int n;
int route_node[MAXN];
vector<int> graph_edges[MAXN];
long long answer[MAXN];
int parent_node[MAXN];

void mark_path(int start, int target) {
    for (int i = 1; i <= n; i++) {
        parent_node[i] = -1;
    }
    queue<int> que;
    que.push(start);
    parent_node[start] = 0;

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        if (u == target) {
            break;
        }
        for (int i = 0; i < (int)graph_edges[u].size(); i++) {
            int v = graph_edges[u][i];
            if (parent_node[v] == -1) {
                parent_node[v] = u;
                que.push(v);
            }
        }
    }

    int x = target;
    while (x != 0) {
        answer[x]++;
        if (x == start) {
            break;
        }
        x = parent_node[x];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> route_node[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph_edges[u].push_back(v);
        graph_edges[v].push_back(u);
    }

    for (int i = 1; i < n; i++) {
        mark_path(route_node[i], route_node[i + 1]);
    }
    for (int i = 2; i <= n; i++) {
        answer[route_node[i]]--;
    }

    for (int i = 1; i <= n; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int LOG = 20;

int n;
int route_node[MAXN];
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;
int depth_node[MAXN];
int up[MAXN][LOG + 1];
long long diff_count[MAXN];
long long answer[MAXN];

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void read_input() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> route_node[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
}

void build_lca() {
    queue<int> que;
    que.push(1);
    depth_node[1] = 1;

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int j = 1; j <= LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == up[u][0]) {
                continue;
            }
            up[v][0] = u;
            depth_node[v] = depth_node[u] + 1;
            que.push(v);
        }
    }
}

int lca(int x, int y) {
    if (depth_node[x] < depth_node[y]) {
        swap(x, y);
    }

    int diff = depth_node[x] - depth_node[y];
    for (int j = LOG; j >= 0; j--) {
        if ((diff & (1 << j)) != 0) {
            x = up[x][j];
        }
    }

    if (x == y) {
        return x;
    }

    for (int j = LOG; j >= 0; j--) {
        if (up[x][j] != up[y][j]) {
            x = up[x][j];
            y = up[y][j];
        }
    }
    return up[x][0];
}

void collect_answer() {
    vector<int> order;
    order.reserve(n);
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        order.push_back(u);
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == up[u][0]) {
                continue;
            }
            que.push(v);
        }
    }

    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        answer[u] += diff_count[u];
        if (up[u][0] != 0) {
            diff_count[up[u][0]] += diff_count[u];
        }
    }
}

void solve() {
    build_lca();

    for (int i = 1; i < n; i++) {
        int u = route_node[i];
        int v = route_node[i + 1];
        int g = lca(u, v);
        diff_count[u]++;
        diff_count[v]++;
        diff_count[g]--;
        if (up[g][0] != 0) {
            diff_count[up[g][0]]--;
        }
    }

    collect_answer();

    // 每个中间到达点既是上一段终点又是下一段起点，只应拿一次糖。
    for (int i = 2; i <= n; i++) {
        answer[route_node[i]]--;
    }

    for (int i = 1; i <= n; i++) {
        cout << answer[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}