#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define vii vector<pair<int,int>>
#define vi vector<int>
const int MAXN = 1e5 + 5;
struct d{
int a;
int b;
int dist;
};
int n, m, q;
int miejsca[MAXN];
vector<pii> graf[MAXN];
int odlodroota[MAXN];
int gl[MAXN];
int pre[MAXN];
int post[MAXN];
int przodek[MAXN][17];
int wartoscpre[MAXN];
vector<d> szuk;
int cnt = 0;
int it = 0;
set<int> tmp;
vector<int> uzyteczne;
void dfs(int v, int p){
pre[v] = cnt;
wartoscpre[cnt] = v;
//cout << v << " " << pre[v] << " pre\n";
post[v] = cnt;
cnt++;
for(auto u : graf[v]){
if(u.first == p) continue;
gl[u.first] = gl[v] + 1;
przodek[u.first][0] = v;
odlodroota[u.first] = odlodroota[v] + u.second;
for(int j = 1; j < 17; ++j){
przodek[u.first][j] = przodek[przodek[u.first][j-1]][j-1];
}
dfs(u.first, v);
post[v] = post[u.first];
}
return;
}
int obliczLCA(int x, int y){
if(x == y) return x;
if(gl[x] < gl[y]) swap(x, y);
for(int i = 16; i >= 0; --i){
if(gl[x] - (1 << i) >= gl[y]){
x = przodek[x][i];
}
}
if(x == y) return x;
for(int i = 16; i >= 0; --i){
if(gl[x] >= (1 << i) and przodek[x][i] != przodek[y][i]){
x = przodek[x][i];
y = przodek[y][i];
}
}
return przodek[x][0];
}
void dfs2(int v, int p){
bool c = (it != uzyteczne.size() and wartoscpre[uzyteczne[it]] == v);
if(c) ++it;
int last = -1;
for(auto u : graf[v]){
if(u.first == p) continue;
if(c and it != last and it != uzyteczne.size() and uzyteczne[it] >= pre[v] and uzyteczne[it] <= post[v]){
//cout << v << " " << wartoscpre[uzyteczne[it]] << " nowa kraw do grafu\n";
szuk.push_back({v, wartoscpre[uzyteczne[it]], odlodroota[wartoscpre[uzyteczne[it]]] - odlodroota[v]});
last = it;
}
dfs2(u.first, v);
}
return;
}
void generujkrawedzie(const vector<d> &starekrawedzie, int nowyroot, int poczatekmiejsc, int koniecmiejsc){
if(poczatekmiejsc >= koniecmiejsc) {
szuk.clear();
return;
}
cnt = 0;
it = 0;
szuk.clear();
uzyteczne.clear();
tmp.clear();
for(auto u : starekrawedzie){
graf[u.a].push_back({u.b, u.dist});
graf[u.b].push_back({u.a, u.dist});
}
dfs(nowyroot, -1);
//cout << poczatekmiejsc << " " << koniecmiejsc << " pk\n";
for(int i = poczatekmiejsc; i <= koniecmiejsc; ++i){
if(pre[miejsca[i]] != 0) {
uzyteczne.push_back(pre[miejsca[i]]);
}
}
sort(uzyteczne.begin(),uzyteczne.end());
for(int i = 0; i < uzyteczne.size()-1; ++i){
int x = wartoscpre[uzyteczne[i]];
int y = wartoscpre[uzyteczne[i+1]];
//cout << x << " " << y << " gen LCA\n";
int LCA = obliczLCA(x, y);
//cout << LCA << " LCA\n";
tmp.insert(pre[LCA]);
}
for(auto u : uzyteczne){
tmp.insert(u);
}
tmp.insert(0);
uzyteczne.clear();
for(auto u : tmp){
uzyteczne.push_back(u);
}
dfs2(nowyroot, -1);
for(auto u : starekrawedzie){
for(auto t : {u.a, u.b}){
graf[t].clear();
pre[t] = 0;
post[t] = 0;
odlodroota[t] = 0;
for(int i = 0; i < 17; ++i){
przodek[t][i] = 0;
}
gl[t] = 0;
}
}
for(int i = 0; i < cnt; ++i){
wartoscpre[i] = 0;
}
// for(auto u : szuk){
// cout << u.a << " " << u.b << " " << u.dist << " U\n";
// }
return;
}
struct e{
int l;
int r;
int org;
};
int ans[MAXN];
pii przedzialy[MAXN];
struct f{
int l;
int r;
int typ;
int last;
};
vector<f> sweep;
const int base = 1 << 17;
int drzew[base << 1];
void akt(int w, int val){
w += base;
while(w != 0){
drzew[w] += val;
w /= 2;
}
return;
}
int obl(int w, int a, int b, int akt_a, int akt_b){
if(a <= akt_a and akt_b <= b) return drzew[w];
if(akt_a > b or akt_b < a) return 0;
int mid = (akt_a + akt_b) / 2;
return obl(2 * w, a, b, akt_a, mid) + obl(2 * w + 1, a, b, mid + 1, akt_b);
}
set<int> ind[MAXN];
void dfs3(int v, int p, int mid, int koszt){
if(ind[v].size() == 0) przedzialy[v] = {0, n + 1};
else{
auto it = ind[v].upper_bound(mid);
if(it == ind[v].begin()) przedzialy[v].first = 0;
else przedzialy[v].first = *(--it);
it = ind[v].upper_bound(mid);
if(it == ind[v].end()) przedzialy[v].second = n+1;
else przedzialy[v].second = *it;
}
for(auto u : graf[v]){
if(u.first == p) continue;
dfs3(u.first, v, mid, u.second);
przedzialy[v].first = max(przedzialy[v].first, przedzialy[u.first].first);
przedzialy[v].second = min(przedzialy[v].second, przedzialy[u.first].second);
}
if(v != miejsca[mid]){
//cout << v << " " << przedzialy[v].first << " " << przedzialy[v].second << " przedzial\n";
//cout << przedzialy[v].first << " " << koszt << " ADDDDD\n";
akt(przedzialy[v].first, koszt);
sweep.push_back({przedzialy[v].first, przedzialy[v].second, 0, koszt});
}
return;
}
bool comp(const f &f1, const f &f2){
if(f1.r != f2.r) return f1.r < f2.r;
if(f1.typ != f2.typ) return f1.typ < f2.typ;
return false;
}
void daq(const vector<d> &kraw, int root, int l, int r, vector<e> &queries){
if(l > r){
//cout << l << " " << r << " zly\n";
return;
}
if(l == r){
//cout << l << " " << r << " rowny\n";
for(auto u : queries){
ans[u.org] = 1;
}
return;
}
// cout << root << " " << l << " " << r << " lr\n";
// for(auto u : kraw){
// cout << u.a << " " << u.b << " " << u.dist << " graf\n";
// }
for(int i = l; i <= r; ++i){
ind[miejsca[i]].insert(i);
}
vector<e> lewe;
vector<e> prawe;
vector<e> reszta;
int split = (l + r) / 2;
for(auto u : queries){
if(u.r < split) lewe.push_back(u);
else if(u.l > split) prawe.push_back(u);
else reszta.push_back(u);
}
for(auto u : kraw){
graf[u.a].push_back({u.b, u.dist});
graf[u.b].push_back({u.a, u.dist});
}
int mid = (l + r) / 2;
dfs3(root, -1, mid, -1);
for(auto u : reszta){
//cout << u.l << " " << u.r << " " << u.org << " zap\n";
sweep.push_back({u.l, u.r, 1, u.org});
}
sort(sweep.begin(),sweep.end(),comp);
ll S = 0;
for(auto u : sweep){
if(u.typ == 0){
akt(u.l, -u.last);
S += u.last;
}
else{
ans[u.last] = obl(1, u.l, mid, 0, base - 1) + S + 1;
}
}
sweep.clear();
for(auto u : kraw){
graf[u.a].clear();
graf[u.b].clear();
przedzialy[u.a] = {0, 0};
przedzialy[u.b] = {0, 0};
}
for(int i = l; i <= r; ++i){
ind[miejsca[i]].clear();
}
// cout << l << " " << mid - 1 << " p1\n";
// cout << mid + 1 << " " << r << " p2\n";
if(l <= mid - 1) generujkrawedzie(kraw, miejsca[(l + mid - 1) / 2], l, mid - 1);
vector<d> G1 = szuk;
if(mid + 1 <= r) generujkrawedzie(kraw, miejsca[(mid + 1 + r) / 2], mid + 1, r);
vector<d> G2 = szuk;
if(l <= mid - 1) daq(G1, miejsca[(l + mid - 1) / 2], l, mid - 1, lewe);
if(mid + 1 <= r) daq(G2, miejsca[(mid + 1 + r) / 2], mid + 1, r, prawe);
return;
}
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
cin >> n >> m >> q;
vector<d> kraw;
int a, b;
for(int i = 0; i < n-1; ++i){
cin >> a >> b;
kraw.push_back({a, b, 1});
}
for(int i = 1; i <= m; ++i){
cin >> miejsca[i];
}
vector<e> zap;
for(int i = 1; i <= q; ++i){
cin >> a >> b;
zap.push_back({a, b, i});
}
generujkrawedzie(kraw, miejsca[(m+1)/2], 1, m);
auto G = szuk;
daq(G, miejsca[(m + 1) / 2], 1, m, zap);
for(int i = 1; i <= q; ++i){
cout << ans[i] << " ";
}
cout << "\n";
return 0;
}
