#include <bits/stdc++.h>
using namespace std;
// --- GLOBAL DATA STRUCTURES ---
// We use 1-indexing for the cities.
int N, M;
vector<vector<int>> adj; // tree: for each city, its adjacent cities
vector<int> speciality; // speciality[i] is the speciality produced at city i
// --- MEMOIZATION FOR THE "CHAIN" (directed edge) ---
// For each directed edge (x -> u), we want to store the chain (as a vector<int>)
// defined by:
// f(x,u)[1] = u,
// and if (u, v) is the unique continuation (i.e. among u’s neighbors excluding x, if there is exactly one neighbor v)
// then for d>=2: f(x,u)[d] = f(u,v)[d-1],
// otherwise the chain stops.
// We use a key for a directed edge.
struct EdgeKey {
int u, v; // u -> v (starting at u then going to v)
bool operator==(const EdgeKey &other) const {
return u == other.u && v == other.v;
}
};
struct EdgeKeyHash {
std::size_t operator()(const EdgeKey &ek) const {
return ((size_t)ek.u) * 100007ULL + ek.v;
}
};
// memo: maps the directed edge (x -> u) to the chain vector.
unordered_map<EdgeKey, vector<int>, EdgeKeyHash> memo;
// Recursive function: getChain(x,u) returns the chain (as a vector<int>) for the directed edge x->u.
vector<int> getChain(int x, int u) {
EdgeKey key = {x, u};
if(memo.find(key) != memo.end())
return memo[key];
vector<int> chain;
// The first city in the chain is u (at distance 1 from x).
chain.push_back(u);
// Now, see if we can extend the chain.
// Look at u’s neighbors except x.
int cnt = 0;
int next = -1;
for (int w : adj[u]) {
if (w == x) continue;
cnt++;
next = w;
}
// If there is exactly one neighbor (i.e. the branch is a chain) then extend.
if (cnt == 1) {
vector<int> rest = getChain(u, next);
chain.insert(chain.end(), rest.begin(), rest.end());
}
memo[key] = chain;
return chain;
}
// --- MAIN ---
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
// Read the tree
adj.assign(N+1, vector<int>());
for (int i=1; i<=N-1; i++){
int A, B;
cin >> A >> B;
adj[A].push_back(B);
adj[B].push_back(A);
}
cin >> M;
// Read the speciality produced at each city.
// (Cities are numbered 1..N.)
speciality.resize(N+1);
for (int i=1; i<=N; i++){
cin >> speciality[i];
}
// ans[x] will store the answer for city x.
vector<int> ans(N+1, 0);
// Process each city x.
// For city x, the idea is:
// - For every neighbor u of x, compute L(x,u) = (length of the chain from x->u)
// - If x is a leaf (degree 1), then the unique branch is the only branch and unique distances are 1..L(x,u).
// - Otherwise, let L1 = maximum chain length among neighbors,
// and let L2 = the second maximum (or 0 if x has only one neighbor).
// Then if the maximum L1 is unique (i.e. only one neighbor attains L1) the unique distances are
// d = L2+1, L2+2, …, L1.
// - Finally, “read off” the cities at these distances from the chain that gave L1 and count distinct specialities.
for (int x = 1; x <= N; x++){
int deg = adj[x].size();
if(deg == 0) { // should not happen in a connected tree
ans[x] = 0;
continue;
}
// branchInfo: for each neighbor u of x, store pair {chain length, neighbor u}
vector<pair<int,int>> branchInfo;
for (int u : adj[x]){
vector<int> chain = getChain(x, u);
int len = chain.size(); // note: len is the maximum distance from x along branch u
branchInfo.push_back({len, u});
}
if(deg == 1){
// Only one branch. Then unique distances are 1..L, where L = chain length.
int L1 = branchInfo[0].first;
vector<int> chain = getChain(x, branchInfo[0].second);
unordered_set<int> specSet;
// d=1 corresponds to chain[0], d=2 to chain[1], …, d=L1 to chain[L1-1].
for (int d = 1; d <= L1; d++){
specSet.insert(speciality[ chain[d-1] ]);
}
ans[x] = specSet.size();
} else {
// x has at least two neighbors.
int L1 = -1, L2 = -1;
int countMax = 0; // count how many branches attain the maximum length L1.
int bestNeighbor = -1;
for (auto &p : branchInfo){
int L = p.first;
if(L > L1){
L2 = L1;
L1 = L;
bestNeighbor = p.second;
countMax = 1;
} else if(L == L1){
countMax++;
} else if(L > L2){
L2 = L;
}
}
// If the maximum chain length appears at least twice then no distance d has S_x(d)==1.
if(countMax != 1){
ans[x] = 0;
} else {
// Unique distances for x are d = L2+1, L2+2, …, L1.
vector<int> chain = getChain(x, bestNeighbor);
unordered_set<int> specSet;
// d (1-indexed) means chain index (d-1).
for (int d = L2+1; d <= L1; d++){
specSet.insert(speciality[ chain[d-1] ]);
}
ans[x] = specSet.size();
}
}
}
// Output the answer for each city.
for (int i=1; i<=N; i++){
cout << ans[i] << "\n";
}
return 0;
}
