/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct query
{
int l, r, idx;
} task[maxn];
int n, m, c[maxn], q;
vector < int > adj[maxn];
void input()
{
cin >> n >> m >> q;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
for (int i = 1; i <= m; i ++)
{
cin >> c[i];
}
for (int i = 1; i <= q; i ++)
{
cin >> task[i].l >> task[i].r;
task[i].idx = i;
}
}
int depth[maxn], tin[maxn], tout[maxn];
int occ[2 * maxn], rev[2 * maxn], timer;
void euler(int v = 1, int p = - 1)
{
occ[++ timer] = v;
tin[v] = timer;
rev[timer] = v;
for (int u : adj[v])
{
if (u == p)
continue;
depth[u] = depth[v] + 1;
euler(u, v);
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 20;
int lg[2 * maxn], dp[maxlog][2 * maxn];
void sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = occ[i];
}
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= timer - (1 << j); i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int get_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1;
int lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
int get_distance(int v, int u)
{
return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}
/**bool cmp_tin(int v, int u)
{
return tin[v] < tin[u];
}
void solve_query(int lf, int rf)
{
vector < int > ord;
int global_lca = c[lf];
for (int i = lf; i <= rf; i ++)
{
ord.push_back(c[i]);
global_lca = get_lca(global_lca, c[i]);
}
sort(ord.begin(), ord.end(), cmp_tin);
int ans = 0;
for (int i = 0; i < ord.size(); i ++)
{
ans = ans + depth[ord[i]] - depth[global_lca];
if (i > 0)
{
ans = ans - (depth[get_lca(ord[i - 1], ord[i])] - depth[global_lca]);
}
}
cout << ans + 1 << endl;
}*/
int block_size = sqrt(maxn);
bool cmp_mo(query a, query b)
{
if (a.l / block_size == b.l / block_size)
return a.r < b.r;
return a.l / block_size < b.l / block_size;
}
int lf = 1, rf, cost;
int fen[2 * maxn], act_cnt[maxn];
void update(int v, int val)
{
//cout << "update " << val << endl;
for (int i = v; i <= timer; i += (i & -i))
fen[i] += val;
}
int query_sum(int v)
{
int s = 0;
for (int i = v; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
int get_kth(int k)
{
if (k == 0) /// corner case?
return 0;
///cout << "get_kth " << k << endl;
int sum = 0, pos = 0;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if ((pos | (1 << bit)) > timer)
continue;
int new_pos = (pos | (1 << bit));
///cout << "transition " << pos << " " << new_pos << " " << sum + fen[new_pos] << " " << fen[new_pos] << endl;
if (sum + fen[new_pos] < k)
{
sum = sum + fen[new_pos];
pos = new_pos;
}
}
return pos + 1;
}
void add_vertex(int ver)
{
act_cnt[ver] ++;
if (act_cnt[ver] > 1)
return;
int sm = query_sum(tin[ver]);
int bef = get_kth(sm);
int aft = get_kth(sm + 1);
///cout << "add " << rev[bef] << " " << ver << " " << rev[aft] << endl;
if (bef != 0 && aft != timer + 1)
cost = cost + depth[get_lca(rev[bef], rev[aft])];
cost = cost + depth[ver];
if (bef != 0)
cost = cost - depth[get_lca(rev[bef], ver)];
if (aft != timer + 1)
cost = cost - depth[get_lca(ver, rev[aft])];
update(tin[ver], 1);
}
void remove_vertex(int ver)
{
act_cnt[ver] --;
if (act_cnt[ver] > 0)
return;
update(tin[ver], -1);
int sm = query_sum(tin[ver]);
int bef = get_kth(sm);
int aft = get_kth(sm + 1);
///cout << "rem " << rev[bef] << " " << ver << " " << rev[aft] << endl;
if (bef != 0 && aft != timer + 1)
cost = cost - depth[get_lca(rev[bef], rev[aft])];
cost = cost - depth[ver];
if (bef != 0)
cost = cost + depth[get_lca(rev[bef], ver)];
if (aft != timer + 1)
cost = cost + depth[get_lca(ver, rev[aft])];
}
void solve_query(int l, int r)
{
while(rf < r)
{
rf ++;
add_vertex(c[rf]);
}
while(lf > l)
{
lf --;
add_vertex(c[lf]);
}
while(rf > r)
{
remove_vertex(c[rf]);
rf --;
}
while(lf < l)
{
remove_vertex(c[lf]);
lf ++;
}
}
int tree[4 * maxn];
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root] = c[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = get_lca(tree[root * 2], tree[root * 2 + 1]);
}
int query_lca(int root, int left, int right, int qleft, int qright)
{
if (left == qleft && right == qright)
return tree[root];
int mid = (left + right) / 2;
if (qright <= mid)
return query_lca(root * 2, left, mid, qleft, qright);
if (qleft > mid)
return query_lca(root * 2 + 1, mid + 1, right, qleft, qright);
return get_lca(query_lca(root * 2, left, mid, qleft, mid),
query_lca(root * 2 + 1, mid + 1, right, mid + 1, qright));
}
int res[maxn];
void queries()
{
block_size = sqrt(m);
build_tree(1, 1, m);
sort(task + 1, task + q + 1, cmp_mo);
for (int i = 1; i <= q; i ++)
{
solve_query(task[i].l, task[i].r);
///cout << "cost " << cost << endl;
///if (i == 2)exit(0);
int global_lca = query_lca(1, 1, m, task[i].l, task[i].r);
//for (int j = task[i].l; j <= task[i].r; j ++)
// global_lca = get_lca(global_lca, c[j]);
res[task[i].idx] = cost - depth[global_lca] + 1;
}
for (int i = 1; i <= q; i ++)
cout << res[i] << endl;
}
void solve()
{
input();
euler();
sparse_table();
queries();
}
int main()
{
speed();
solve();
return 0;
}
