#include <bits/stdc++.h> using namespace std; #define POPCOUNT(n) (__builtin_popcountll((n))) #define CLZ(n) (__builtin_clzll((n))) #define CTZ(n) (__builtin_ctzll((n))) #define LOG(n) (63 - __builtin_clzll((n))) #define BIT(n, i) (((n) >> (i)) & 1ll) #define MASK(i) (1ll << (i)) #define FLIP(n, i) ((n) ^ (1ll << (i))) #define ON(n, i) ((n) | MASK(i)) #define OFF(n, i) ((n) & ~MASK(i)) #define Int __int128 #define fi first #define se second typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef pair<long long, int> pli; typedef pair<int, long long> pil; typedef vector<pair<int, int>> vii; typedef vector<pair<long long, long long>> vll; typedef vector<pair<long long, int>> vli; typedef vector<pair<int, long long>> vil; template <class T1, class T2> bool maximize(T1 &x, T2 y) { if (x < y) { x = y; return true; } return false; } template <class T1, class T2> bool minimize(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } template <class T> void remove_duplicate(vector<T> &ve) { sort (ve.begin(), ve.end()); ve.resize(unique(ve.begin(), ve.end()) - ve.begin()); } mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); long long random(long long l, long long r) { return uniform_int_distribution<long long>(l, r)(rng); } unsigned long long random(unsigned long long l, unsigned long long r) { return uniform_int_distribution<unsigned long long>(l, r)(rng); } template <class T> T random(T r) { return rng() % r; } const int N = 1e6 + 5; const int MOD = 1e9 + 7; const int inf = 1e9; const long long INF = 1e18; int n, m, q, dfsTime; int c[N], ans[N], par[N], dep[N], heavy[N], head[N], pos[N]; vector<int> adj[N]; vii que[N]; int dfs(int u, int fa) { int ma = -1, sz = 1; heavy[u] = -1; for (auto v : adj[u]) if (v != fa) { par[v] = u, dep[v] = dep[u] + 1; int tmp = dfs(v, u); sz += tmp; if (maximize(ma, tmp)) heavy[u] = v; } return sz; } void hld(int u, int uhead) { head[u] = uhead, pos[u] = ++dfsTime; if (heavy[u] != -1) hld(heavy[u], heavy[u]); for (auto v : adj[u]) if (v != par[u] && v != heavy[u]) { hld(v, v); } } struct FenwickTree { using T = int; vector<T> bit; FenwickTree() {} void resize(int n) { bit.assign(n + 1, 0); } void update(int p, T val) { for (; p < int(bit.size()); p += p & -p) bit[p] += val; } T get(int p) { T ans = 0; for (; p > 0; p -= p & -p) ans += bit[p]; return ans; } T get(int l, int r) { return get(r) - get(l - 1); } } fen; int R[N], value[N]; set<int> s; void add(int l, int r, int val) { fen.update(val, r - l + 1); R[l] = r, value[l] = val; s.emplace(l); } void rem(int l, int r, int val) { fen.update(val, -(r - l + 1)); s.erase(s.find(l)); } void change(int l, int r, int val) { auto it = s.lower_bound(l); if (it != s.begin()) { it = prev(it); int tL = *it, tR = R[*it]; if (l <= R[*it]) { rem(tL, tR, value[tL]); add(tL, l - 1, value[tL]); } } it = s.lower_bound(l); if (it != s.end() && *it <= r) { auto work = [&](set<int>::iterator it) { if (R[*it] > r) { int tL = *it, tR = R[*it], tVal = value[*it]; rem(tL, tR, tVal); add(r + 1, tR, tVal); } else rem(*it, R[*it], value[*it]); }; while (next(it) != s.end() && *next(it) <= r) { work(next(it)); } work(it); } add(l, r, val); } void update(int u, int v, int val) { for (; head[u] != head[v]; v = par[head[v]]) { if (dep[head[u]] > dep[head[v]]) swap(u, v); change(pos[head[v]], pos[v], val); } if (pos[u] > pos[v]) swap(u, v); change(pos[u] + 1, pos[v], val); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> q; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); } dfs(1, -1); hld(1, 1); for (int i = 1; i <= m; ++i) cin >> c[i]; for (int i = 1; i <= q; ++i) { int l, r; cin >> l >> r; if (l == r) { ans[i] = 1; continue; } que[r].emplace_back(l, i); } fen.resize(n); for (int r = 2; r <= n; ++r) { update(c[r - 1], c[r], r - 1); for (auto [l, id] : que[r]) ans[id] = fen.get(l, n) + 1; } for (int i = 1; i <= q; ++i) cout << ans[i] << '\n'; return 0; }