#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100000 + 5;
const int LOGE = 20;
struct FastScanner {
static const int S = 1 << 20;
int idx, size;
char buf[S];
FastScanner() : idx(0), size(0) {}
inline char getChar() {
if (idx >= size) {
size = fread(buf, 1, S, stdin);
idx = 0;
if (size == 0) return 0;
}
return buf[idx++];
}
template<class T>
inline bool readInt(T &out) {
char c;
T sign = 1;
T num = 0;
c = getChar();
if (!c) return false;
while (c != '-' && (c < '0' || c > '9')) {
c = getChar();
if (!c) return false;
}
if (c == '-') {
sign = -1;
c = getChar();
}
while (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
c = getChar();
}
out = num * sign;
return true;
}
};
int n, m, q;
vector<int> adj[MAXN];
int c[MAXN];
int tin[MAXN], firstOcc[MAXN], depthArr[MAXN], tinToNode[MAXN], cntNode[MAXN];
int timerDfs;
vector<int> euler;
int lg2_[2 * MAXN];
int st[LOGE][2 * MAXN];
inline int betterDepth(int a, int b) {
return depthArr[a] < depthArr[b] ? a : b;
}
void buildDfsIterative() {
vector<int> parent(n + 1, 0), it(n + 1, 0), stk;
stk.reserve(n);
timerDfs = 0;
euler.clear();
euler.reserve(2 * n);
stk.push_back(1);
parent[1] = 0;
depthArr[1] = 0;
tin[1] = timerDfs;
tinToNode[timerDfs] = 1;
timerDfs++;
firstOcc[1] = 0;
euler.push_back(1);
while (!stk.empty()) {
int u = stk.back();
if (it[u] == (int)adj[u].size()) {
stk.pop_back();
if (!stk.empty()) euler.push_back(stk.back());
continue;
}
int v = adj[u][it[u]++];
if (v == parent[u]) continue;
parent[v] = u;
depthArr[v] = depthArr[u] + 1;
tin[v] = timerDfs;
tinToNode[timerDfs] = v;
timerDfs++;
firstOcc[v] = (int)euler.size();
euler.push_back(v);
stk.push_back(v);
}
}
void buildLca() {
int sz = (int)euler.size();
lg2_[1] = 0;
for (int i = 2; i <= sz; i++) lg2_[i] = lg2_[i >> 1] + 1;
for (int i = 0; i < sz; i++) st[0][i] = euler[i];
for (int k = 1; k < LOGE; k++) {
int len = 1 << k;
int half = len >> 1;
for (int i = 0; i + len <= sz; i++) {
st[k][i] = betterDepth(st[k - 1][i], st[k - 1][i + half]);
}
}
}
inline int lca(int u, int v) {
int l = firstOcc[u];
int r = firstOcc[v];
if (l > r) swap(l, r);
int k = lg2_[r - l + 1];
return betterDepth(st[k][l], st[k][r - (1 << k) + 1]);
}
inline int distTree(int u, int v) {
int w = lca(u, v);
return depthArr[u] + depthArr[v] - 2 * depthArr[w];
}
ll hilbertOrder(int x, int y, int pow = 17, int rot = 0) {
if (pow == 0) return 0;
int hpow = 1 << (pow - 1);
int seg;
if (x < hpow) {
seg = (y < hpow ? 0 : 3);
} else {
seg = (y < hpow ? 1 : 2);
}
seg = (seg + rot) & 3;
static const int rotateDelta[4] = {3, 0, 0, 1};
int nx = x & (hpow - 1);
int ny = y & (hpow - 1);
int nrot = (rot + rotateDelta[seg]) & 3;
ll subSquareSize = 1LL << (2 * pow - 2);
ll ord = seg * subSquareSize;
ll add = hilbertOrder(nx, ny, pow - 1, nrot);
if (seg == 1 || seg == 2) ord += add;
else ord += subSquareSize - add - 1;
return ord;
}
struct Query {
int l, r, id;
ll ord;
};
set<int> activeTin;
ll curans = 0;
inline int nodeFromTin(int t) {
return tinToNode[t];
}
inline void activateNode(int v) {
int t = tin[v];
if (activeTin.empty()) {
activeTin.insert(t);
return;
}
auto it = activeTin.lower_bound(t);
int nxtTin = (it == activeTin.end() ? *activeTin.begin() : *it);
int prvTin;
if (it == activeTin.begin()) prvTin = *activeTin.rbegin();
else {
auto jt = it;
--jt;
prvTin = *jt;
}
int prv = nodeFromTin(prvTin);
int nxt = nodeFromTin(nxtTin);
curans += distTree(prv, v) + distTree(v, nxt) - distTree(prv, nxt);
activeTin.insert(t);
}
inline void deactivateNode(int v) {
int t = tin[v];
if ((int)activeTin.size() == 1) {
activeTin.erase(t);
return;
}
auto it = activeTin.find(t);
auto itPrev = it;
if (itPrev == activeTin.begin()) itPrev = prev(activeTin.end());
else --itPrev;
auto itNext = next(it);
if (itNext == activeTin.end()) itNext = activeTin.begin();
int prv = nodeFromTin(*itPrev);
int nxt = nodeFromTin(*itNext);
curans -= distTree(prv, v) + distTree(v, nxt) - distTree(prv, nxt);
activeTin.erase(it);
}
inline void addPos(int idx) {
int v = c[idx];
cntNode[v]++;
if (cntNode[v] == 1) activateNode(v);
}
inline void removePos(int idx) {
int v = c[idx];
cntNode[v]--;
if (cntNode[v] == 0) deactivateNode(v);
}
int main() {
FastScanner fs;
fs.readInt(n);
fs.readInt(m);
fs.readInt(q);
for (int i = 1; i < n; i++) {
int u, v;
fs.readInt(u);
fs.readInt(v);
adj[u].push_back(v);
adj[v].push_back(u);
}
buildDfsIterative();
buildLca();
for (int i = 0; i < m; i++) fs.readInt(c[i]);
vector<Query> queries(q);
for (int i = 0; i < q; i++) {
int l, r;
fs.readInt(l);
fs.readInt(r);
--l;
--r;
queries[i] = {l, r, i, hilbertOrder(l, r)};
}
sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
return a.ord < b.ord;
});
vector<ll> ans(q);
int L = 0;
int R = -1;
for (const Query &qq : queries) {
while (L > qq.l) addPos(--L);
while (R < qq.r) addPos(++R);
while (L < qq.l) removePos(L++);
while (R > qq.r) removePos(R--);
ans[qq.id] = curans / 2 + 1;
}
string out;
out.reserve(q * 4);
for (int i = 0; i < q; i++) {
out += to_string(ans[i]);
out += '\n';
}
fwrite(out.c_str(), 1, out.size(), stdout);
return 0;
}
