//████████╗██╗███╗░░██╗ ██╗░░░░░███████╗
//╚══██╔══╝██║████╗░██║ ██║░░░░░██╔════╝
//░░░██║░░░██║██╔██╗██║ ██║░░░░░█████╗░░
//░░░██║░░░██║██║╚████║ ██║░░░░░██╔══╝░░
//░░░██║░░░██║██║░╚███║ ███████╗███████╗
//░░░╚═╝░░░╚═╝╚═╝░░╚══╝ ╚══════╝╚══════╝
// __________________
// | ________________ |
// || ____ ||
// || /\ | ||
// || /__\ | ||
// || / \ |____ ||
// ||________________||
// |__________________|
// \###################\
// \###################\
// \ ____ \
// \_______\___\_______\
// An AC a day keeps the doctor away.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#include <functional>
#include <numeric>
#include <stack>
#include <array>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define vt vector
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define ub upper_bound
#define lb lower_bound
#define db double
#define ld long db
#define ll long long
#define ull unsigned long long
#define vll vt<ll>
#define vvll vt<vll>
#define pll pair<ll, ll>
#define vpll vt<pll>
#define vvpll vt<vpll>
#define vc vt<char>
#define vvc vt<vc>
#define vi vt<int>
#define vvi vt<vi>
#define vvvi vt<vvi>
#define pii pair<int, int>
#define vpii vt<pii>
#define vs vt<string>
#define vvs vt<vs>
#define vb vt<bool>
#define vvb vt<vb>
#define vvpii vt<vpii>
#define vd vt<db>
#define ar(x) array<int, x>
#define var(x) vt<ar(x)>
#define vvar(x) vt<var(x)>
#define al(x) array<ll, x>
#define vall(x) vt<al(x)>
#define vvall(x) vt<vall(x)>
#define mset(m, v) memset(m, v, sizeof(m))
#define pb push_back
#define ff first
#define ss second
#define sv string_view
#define MP make_pair
#define MT make_tuple
#define rsz resize
#define sum(x) (ll)accumulate(all(x), 0LL)
#define srt(x) sort(all(x))
#define srtR(x) sort(allr(x))
#define srtU(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
#define SORTED(x) is_sorted(all(x))
#define rev(x) reverse(all(x))
#define MAX(a) *max_element(all(a))
#define MIN(a) *min_element(all(a))
#define ROTATE(a, p) rotate(begin(a), begin(a) + p, end(a))
#define i128 __int128
//SGT DEFINE
#define lc i * 2 + 1
#define rc i * 2 + 2
#define lp lc, left, middle
#define rp rc, middle + 1, right
#define entireTree 0, 0, n - 1
#define midPoint left + (right - left) / 2
#define pushDown push(i, left, right)
#define iter int i, int left, int right
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
struct custom {
static const uint64_t C = 0x9e3779b97f4a7c15; const uint32_t RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
size_t operator()(const std::string& s) const { size_t hash = std::hash<std::string>{}(s); return hash ^ RANDOM; } };
template <class K, class V> using umap = std::unordered_map<K, V, custom>; template <class K> using uset = std::unordered_set<K, custom>;
template<class T> using max_heap = priority_queue<T>;
template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& arr) {
for (size_t i = 0; i < N; i++) { is >> arr[i]; } return is;
}
template<typename T, size_t N>
istream& operator>>(istream& is, vector<array<T, N>>& vec) {
for (auto &arr : vec) { is >> arr; } return is;
}
template <typename T1, typename T2> istream &operator>>(istream& in, pair<T1, T2>& input) { return in >> input.ff >> input.ss; }
template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &el : v) in >> el; return in; }
template<class T>
void output_vector(vt<T>& a, int off_set = 0) {
int n = a.size();
for(int i = off_set; i < n; i++) {
cout << a[i] << (i == n - 1 ? '\n' : ' ');
}
}
template<typename T, typename Compare>
vi closest_left(const vt<T>& a, Compare cmp) {
int n = a.size(); vi closest(n); iota(all(closest), 0);
for (int i = 0; i < n; i++) {
auto& j = closest[i];
while(j && cmp(a[i], a[j - 1])) j = closest[j - 1];
}
return closest;
}
template<typename T, typename Compare> // auto right = closest_right<int>(a, std::less<int>());
vi closest_right(const vt<T>& a, Compare cmp) {
int n = a.size(); vi closest(n); iota(all(closest), 0);
for (int i = n - 1; i >= 0; i--) {
auto& j = closest[i];
while(j < n - 1 && cmp(a[i], a[j + 1])) j = closest[j + 1];
}
return closest;
}
template<typename T, typename V = string>
vt<pair<T, int>> encode(const V& s) {
vt<pair<T, int>> seg;
for(auto& ch : s) {
if(seg.empty() || ch != seg.back().ff) seg.pb({ch, 1});
else seg.back().ss++;
}
return seg;
}
template<typename K, typename V>
auto operator<<(std::ostream &o, const std::map<K, V> &m) -> std::ostream& {
o << "{"; int i = 0;
for (const auto &[key, value] : m) { if (i++) o << " , "; o << key << " : " << value; }
return o << "}";
}
#ifdef LOCAL
#define debug(x...) debug_out(#x, x)
void debug_out(const char* names) { std::cerr << std::endl; }
template <typename T, typename... Args>
void debug_out(const char* names, T value, Args... args) {
const char* comma = strchr(names, ',');
std::cerr << "[" << (comma ? std::string(names, comma) : names) << " = " << value << "]";
if (sizeof...(args)) { std::cerr << ", "; debug_out(comma + 1, args...); }
else { std::cerr << std::endl; }
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& o, const std::pair<T1, T2>& p) { return o << "{" << p.ff << " , " << p.ss << "}"; }
auto operator<<(auto &o, const auto &x) -> decltype(end(x), o) {
o << "{"; int i = 0; for (const auto &e : x) { if (i++) o << " , "; o << e; } return o << "}";
} // remove for leetcode
#include <sys/resource.h>
#include <sys/time.h>
void printMemoryUsage() {
struct rusage usage;
getrusage(RUSAGE_SELF, &usage);
double memoryMB = usage.ru_maxrss / 1024.0;
cerr << "Memory usage: " << memoryMB << " MB" << "\n";
}
#define startClock clock_t tStart = clock();
#define endClock std::cout << std::fixed << std::setprecision(10) << "\nTime Taken: " << (double)(clock() - tStart) / CLOCKS_PER_SEC << " seconds" << std::endl;
#else
#define debug(...)
#define startClock
#define endClock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define eps 1e-9
#define M_PI 3.14159265358979323846
const static string pi = "3141592653589793238462643383279";
const static ll INF = 1LL << 62;
const static int inf = 1e9 + 100;
const static int MK = 20;
const static int MX = 1e5 + 5;
ll gcd(ll a, ll b) { while (b != 0) { ll temp = b; b = a % b; a = temp; } return a; }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
int pct(ll x) { return __builtin_popcountll(x); }
ll have_bit(ll x, int b) { return x & (1LL << b); }
int min_bit(ll x) { return __builtin_ctzll(x); }
int max_bit(ll x) { return 63 - __builtin_clzll(x); }
const vvi dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}}; // UP, DOWN, LEFT, RIGHT
const vc dirChar = {'U', 'D', 'L', 'R'};
int modExpo(ll base, ll exp, ll mod) { ll res = 1; base %= mod; while(exp) { if(exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; }
ll extended_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll d = extended_gcd(b, a % b, y, x); y -= (a / b) * x; return d; }
ll modInv(ll a, ll m) { ll x, y; ll g = extended_gcd(a, m, x, y); if (g != 1) { return -1; } x %= m; if (x < 0) x += m; return x; }
int modExpo_on_string(ll a, string exp, int mod) { ll b = 0; for(auto& ch : exp) b = (b * 10 + (ch - '0')) % (mod - 1); return modExpo(a, b, mod); }
ll sum_even_series(ll n) { return (n / 2) * (n / 2 + 1);}
ll sum_odd_series(ll n) {return n - sum_even_series(n);} // sum of first n odd number is n ^ 2
ll sum_of_square(ll n) { return n * (n + 1) * (2 * n + 1) / 6; } // sum of 1 + 2 * 2 + 3 * 3 + 4 * 4 + ... + n * n
string make_lower(const string& t) { string s = t; transform(all(s), s.begin(), [](unsigned char c) { return tolower(c); }); return s; }
string make_upper(const string&t) { string s = t; transform(all(s), s.begin(), [](unsigned char c) { return toupper(c); }); return s; }
ll sqrt(ll n) { ll t = sqrtl(n); while(t * t < n) t++; while(t * t > n) t--; return t;}
bool is_perm(ll sm, ll square_sum, ll len) {return sm == len * (len + 1) / 2 && square_sum == len * (len + 1) * (2 * len + 1) / 6;} // determine if an array is a permutation base on sum and square_sum
template<typename T, typename F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n, m;
vt<vt<T>> st;
vi log_table;
F func;
SparseTable() {}
SparseTable(const vt<T>& a, F func) : n(a.size()), func(func) {
m = floor(log2(n)) + 1;
st.rsz(m);
for (int j = 0; j < m; j++) st[j].rsz(n - (1 << j) + 1);
log_table.rsz(n + 1);
for (int i = 2; i <= n; i++) log_table[i] = log_table[i / 2] + 1;
for (int i = 0; i < n; i++) st[0][i] = a[i];
for (int j = 1; j < m; j++) {
for (int i = 0; i + (1 << j) <= n; i++)
st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
T query(int L, int R) {
int j = log_table[R - L + 1];
return func(st[j][L], st[j][R - (1 << j) + 1]);
}
};
template<typename T = int>
struct LCA_O1 {
vi enter;
vpii euler;
SparseTable<pii> st;
int timer;
LCA_O1() {}
LCA_O1(const vt<vt<T>> &graph, int root = 0) : timer(0) {
int n = graph.size();
enter.resize(n, -1);
dfs(root, -1, 0, graph);
st = SparseTable<pii>(euler, [](const pii &a, const pii &b) {
return (a.first < b.first) ? a : b;
});
vpii().swap(euler);
}
void dfs(int node, int par, int d, const vt<vt<T>> &graph) {
enter[node] = timer++;
euler.pb({d, node});
for(auto& nxt : graph[node]) {
if(nxt == par) continue;
dfs(nxt, node, d + 1, graph);
euler.pb({d, node});
timer++;
}
}
int lca(int u, int v) {
int L = min(enter[u], enter[v]);
int R = max(enter[u], enter[v]);
return st.query(L, R).second;
}
};
template<typename T = int>
class GRAPH {
public:
int n, m;
vvi dp;
vi depth, parent, subtree;
vi tin, tout, low, ord;
int timer = 1;
LCA_O1<T> lca_01;
GRAPH() {}
GRAPH(const vt<vt<T>>& graph, int root = 0) : lca_01(graph, root) {
n = graph.size();
m = log2(n) + 1;
dp.rsz(n, vi(m));
depth.rsz(n);
parent.rsz(n, -1);
subtree.rsz(n, 1);
tin.rsz(n);
tout.rsz(n);
ord.rsz(n);
dfs(graph, root);
init();
}
void dfs(const vt<vt<T>>& graph, int node = 0, int par = -1) {
tin[node] = timer++;
ord[tin[node]] = node;
for(auto& nei : graph[node]) {
if(nei == par) continue;
depth[nei] = depth[node] + 1;
dp[nei][0] = node;
parent[nei] = node;
dfs(graph, nei, node);
subtree[node] += subtree[nei];
}
tout[node] = timer - 1;
}
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
void init() {
for(int j = 1; j < m; j++) {
for(int i = 0; i < n; i++) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
int lca(int a, int b) {
return lca_01.lca(a, b);
}
int dist(int u, int v) {
int a = lca_01.lca(u, v);
return depth[u] + depth[v] - 2 * depth[a];
}
int k_ancestor(int a, int k) {
for(int i = m - 1; i >= 0; i--) {
if((k >> i) & 1) a = dp[a][i];
}
return a;
}
int rooted_lca(int a, int b, int c) { // determine if 3 points are in the same path
return lca(a, c) ^ lca(a, b) ^ lca(b, c);
}
int rooted_parent(int u, int v) { // move one level down from u closer to v
return k_ancestor(v, depth[v] - depth[u] - 1);
}
void reroot(int root) {
fill(all(parent), -1);
dfs(root);
init();
}
};
template<class T, typename F = function<T(const T&, const T&)>>
class FW {
public:
int n, N;
vt<T> root;
T DEFAULT;
F func;
FW() {}
FW(int n, T DEFAULT, F func) : func(func) {
this->n = n;
this->DEFAULT = DEFAULT;
N = log2(n);
root.rsz(n, DEFAULT);
}
void update_at(int id, T val) {
assert(id >= 0);
while(id < n) {
root[id] = func(root[id], val);
id |= (id + 1);
}
}
T get(int id) {
assert(id < n);
T res = DEFAULT;
while(id >= 0) {
res = func(res, root[id]);
id = (id & (id + 1)) - 1;
}
return res;
}
T queries_range(int left, int right) {
return get(right) - get(left - 1);
}
T queries_at(int i) {
return queries_range(i, i);
}
void update_range(int l, int r, T val) {
update_at(l, val), update_at(r + 1, -val);
}
void reset() {
root.assign(n, DEFAULT);
}
int select(int x) { // get pos where sum >= x
int global = get(n), curr = 0;
for(int i = N; i >= 0; i--) {
int t = curr ^ (1LL << i);
if(t < n && global - root[t] >= x) {
swap(curr, t);
global -= root[curr];
}
}
return curr + 1;
}
};
void solve() {
int n, m, q; cin >> n >> m >> q;
vpii edges(n);
vvi graph(n + 1);
for(int i = 1; i < n; i++) {
auto& [u, v] = edges[i]; cin >> u >> v;
graph[u].pb(v);
graph[v].pb(u);
}
GRAPH<int> g(graph, 1);
for(int i = 1; i < n; i++) {
auto& [u, v] = edges[i];
if(g.parent[v] != u) swap(u, v);
}
FW<int> root(n + 1, 0, [](const int& a, const int& b) {return a + b;});
for(int i = 1; i <= n; i++) root.update_at(g.tin[i], 1);
auto find_par = [&](int u) -> int {
int x = root.get(g.tin[u]);
int N = g.dp[0].size();
for(int j = N - 1; j >= 0; j--) {
int p = g.dp[u][j];
if(root.get(g.tin[p]) == x) {
u = p;
}
}
return u;
};
vi used(n + 1), ans(n + 1, 1), del(n + 1);
while(m--) {
int k; cin >> k;
auto& [u, v] = edges[k];
if(!used[k]) {
ans[find_par(u)] += ans[v] - del[v];
root.update_range(g.tin[v], g.tout[v], -1);
} else {
ans[v] = del[v] = ans[find_par(u)];
root.update_range(g.tin[v], g.tout[v], 1);
}
used[k] ^= 1;
}
while(q--) {
int u; cin >> u;
assert(u <= n);
cout << ans[find_par(u)] << '\n';
}
}
signed main() {
// careful for overflow, check for long long, use unsigned long long for random generator
// when mle, look if problem require read in file, typically old problems
IOS;
startClock
//generatePrime();
int t = 1;
//cin >> t;
for(int i = 1; i <= t; i++) {
//cout << "Case #" << i << ": ";
solve();
}
endClock
#ifdef LOCAL
printMemoryUsage();
#endif
return 0;
}
//███████████████████████████████████████████████████████████████████████████████████████████████████████
//█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█
//█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█
//█░░▄▀░░░░░░░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░░░░░░░█
//█░░▄▀░░█████████░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░█████████
//█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░█████████
//█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░░░░░█
//█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░█
//█░░▄▀░░█████████░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░█
//█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░▄▀░░█
//█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█
//█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█
//███████████████████████████████████████████████████████████████████████████████████████████████████████
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |