#pragma GCC optimize("O3,unroll-loops")
#include <stdio.h>
#include <stdlib.h>
void pus_(int **eh, int *eo, int x) {
int o = eo[0]++;
if (o == 0)
eh[0] = (int *)malloc(2 * sizeof **eh);
else if ((o & (o - 1)) == 0)
eh[0] = (int *)realloc(eh[0], 2 * o * sizeof **eh);
eh[0][o++] = x;
}
#define pus(eh, eo, x) pus_(&(eh), &(eo), x)
int min(int i, int j) { return i < j ? i : j; }
int max(int i, int j) { return i > j ? i : j; }
#define QQ 100000
#define NN 100000
#define MM 100000
int fw[MM];
void fw_add(int p, int k) {
for (; p < sizeof fw / sizeof *fw; p |= p + 1)
fw[p] += k;
}
long long fw_sum(int p) {
long long z = 0;
for (++p; p > 0; p &= p - 1)
z += fw[p - 1];
return z;
}
int tout[NN], Ans[QQ], N, M, Q, C[MM], L[QQ], R[QQ], X[NN], Y[NN], Freq[NN], *Occ[NN];
int *adj[NN], deg[NN], dfn[NN], timer, dep[NN], jmp[NN], par[NN];
void tree_link(int u, int v) { pus(adj[u], deg[u], v); }
void tree_link_bi(int u, int v) { tree_link(u, v), tree_link(v, u); }
void dfs(int u, int p) {
dep[u] = dep[par[u] = p] + 1;
jmp[u] = (dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]])
? jmp[jmp[p]]
: p;
dfn[u] = timer++;
for (int j = 0; j < deg[u]; ++j)
if (adj[u][j] - p)
dfs(adj[u][j], u);
tout[u] = timer - 1;
}
int lca(int u, int v) {
if (dep[u] < dep[v])
return lca(v, u);
while (dep[u] > dep[v])
u = (dep[jmp[u]] >= dep[v]) ? jmp[u] : par[u];
while (u - v)
if (jmp[u] == jmp[v])
u = par[u], v = par[v];
else
u = jmp[u], v = jmp[v];
return u;
}
int *vtadj[NN], *vtw[NN], vtdeg[NN], vtdeg2[NN];
void virtual_link(int u, int v, int w) {
pus(vtadj[u], vtdeg[u], v);
--vtdeg[u];
pus(vtw[u], vtdeg[u], w);
}
void virtual_link_bi(int u, int v, int w) {
virtual_link(u, v, w), virtual_link(v, u, w);
}
int Compar_Dfn(const void *i, const void *j) {
return dfn[*(const int *)i] - dfn[*(const int *)j];
}
/* in virtual tree, X[u] stores highest k < m such that C[k] == u,
* analogously, Y[u] = stores lowest k > m such that C[k] == u
* this is needed because, we take edge (x, y, w) in virtual tree (rooted at
* C[m]) if query_l <= x or query_r >= y
*
* note that if u is parent of v in virtual tree, even if v's timer more
* permissive than u's timer, we need to take v anyway, so a node's timer need
* to be set at least at strict as it's stricted children */
int vt_up[NN]; /*weight of u, par[u] */
int add_all = 0;
/* note on how to build virtual tree - sort all vertices in dfn order, insert
* lca of every consecutive element, uniqueify the new Vertex List, make the
* tree?? */
void vtdfs(int u, int p, int pw, int m) {
add_all += pw;
vt_up[u] = pw;
/* find upperbound(Occ[u], m); */
int lb = -1, ub = Freq[u];
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (Occ[u][mid] > m)
ub = mid;
else
lb = mid;
}
if (ub < Freq[u])
Y[u] = Occ[u][ub];
if ((ub && Occ[u][--ub] < m) || (ub && Occ[u][--ub] < m))
X[u] = Occ[u][ub];
for (int j = 0; j < vtdeg[u]; ++j)
if (vtadj[u][j] != p) {
vtdfs(vtadj[u][j], u, vtw[u][j], m);
X[u] = max(X[u], X[vtadj[u][j]]);
Y[u] = min(Y[u], Y[vtadj[u][j]]);
}
}
int Compar_Queries_QL_Decreasing(const void *a, const void *b) {
return L[*(const int *)b] - L[*(const int *)a];
}
int Compar_Edges_X_Decreasing(const void *a, const void *b) {
return X[*(const int *)b] - X[*(const int *)a];
}
void rev(int *a, int n) {
int t;
for (int l = 0, r = n - 1; l < r; ++l, --r)
t = a[l], a[l] = a[r], a[r] = t;
}
int mark[NN] = {0}, dnc_timer = 0;
void dnc(int l, int r, int *candidates, int count_candidates) {
if (l >= r)
return; /* ignore l=r because answer is always 1 (ql==qr)*/
int m = l + (r - l) / 2;
/* V = set of vertices in virtual tree , ord = |V| */
/* build a virtual tree for all node u that some l <= k <= r, C[k] = u */
/* collect all interested nodes */
int *V = NULL, ord = 0;
++dnc_timer;
for (int i = l; i <= r; ++i)
if (dnc_timer != mark[C[i]])
(mark[C[i]] = dnc_timer), pus(V, ord, C[i]);
qsort(V, ord, sizeof *V, Compar_Dfn);
for (int orig_ord = ord, lc, i = 1; i < orig_ord; ++i)
if (dnc_timer != mark[lc = lca(V[i], V[i - 1])])
pus(V, ord, lc), mark[lc] = dnc_timer;
qsort(V, ord, sizeof *V, Compar_Dfn);
/* clear global related to virtual tree */
for (int i = 0; i < ord; ++i) {
free(vtadj[V[i]]);
free(vtw[V[i]]);
vtadj[V[i]] = vtw[V[i]] = NULL;
vtdeg[V[i]] = NULL;
add_all = 0;
}
/* build vt */
static int stack[NN << 1], top;
top = 0;
for (int i = 0; i < ord; ++i) {
int u = V[i];
while (top &&
!(dfn[stack[top - 1]] <= dfn[u] && tout[u] <= tout[stack[top - 1]]))
--top;
if (top)
virtual_link_bi(stack[top - 1], u, dep[u] - dep[stack[top - 1]]);
stack[top++] = u;
}
/* do dfs on vt to calculate X and Y */
for (int i = 0; i < ord; ++i)
X[V[i]] = -2, Y[V[i]] = 1e9 + 2;
vtdfs(C[m], -1, 0, m);
/* collect all active queries, one that contain m (ql <= m <= qr) */
int *active = NULL, nactive = 0, *Xt = NULL, nXt = 0, *right = NULL,
nright = 0;
for (int i = 0; i < count_candidates; ++i) {
int j = candidates[i];
if (L[j] <= m && m <= R[j])
pus(active, nactive, j);
else if (R[j] < m)
pus(Xt, nXt, j);
else if (L[j] > m)
pus(right, nright, j);
}
/*
* we add w to queries that ql <= x or y <= qr
* that is , ql <= x , exclusive or (ql > x and y <= qr) */
/* sort active by ql */
/* ql <= x */
qsort(active, nactive, sizeof(int), Compar_Queries_QL_Decreasing);
qsort(V, ord, sizeof(int), Compar_Edges_X_Decreasing);
int pi = 0, sum = 0;
for (int i = 0; i < nactive; ++i) {
int qi = active[i];
while (pi < ord && X[V[pi]] >= L[qi])
sum += vt_up[V[pi++]];
Ans[qi] += sum;
}
/* mutex, ql > x and y <= qr */
rev(active, nactive);
rev(V, ord);
pi = 0;
for (int i = 0; i < nactive; ++i) {
int qi = active[i];
while (pi < ord && X[V[pi]] < L[qi])
fw_add(Y[V[pi]], vt_up[V[pi]]), ++pi;
Ans[qi] += fw_sum(R[qi]);
}
/* undo all fenwick upd (IM GONNA KILLL MYSELF AG IRUH */
pi = 0;
for (int i = 0; i < nactive; ++i) {
int qi = active[i];
while (pi < ord && X[V[pi]] < L[qi])
fw_add(Y[V[pi]], -vt_up[V[pi]]), ++pi;
}
free(V);
free(active);
dnc(l, m, Xt, nXt);
dnc(m + 1, r, right, nright);
free(Xt);
free(right);
}
int main() {
scanf("%d%d%d", &N, &M, &Q);
for (int i = 1, A, B; i < N; ++i)
scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
dfs(0, 0);
for (int i = 0; i < M; ++i)
scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
int *candidates = (int *)malloc(sizeof *candidates * Q);
for (int i = 0; i < Q; ++i)
scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
dnc(0, M - 1, candidates, Q);
free(candidates);
for (int i = 0; i < N; ++i)
free(Occ[i]), free(adj[i]);
for (int i = 0; i < Q; ++i)
printf("%d\n", Ans[i] + 1);
return 0;
}
/*
* https://codeforces.com/blog/entry/114003?#comment-1015100
*
* DNC
*/
