#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 100005
using namespace std;
using ii = pair<int, int>;
const int B = 320;
inline constexpr int csk(const int &x) {return (x-1)/B+1;}
int n, m, q, d[maxn], c[maxn], id = 0, firstOrder[maxn], euler[maxn+maxn];
vector<int> adj[maxn];
ii f[18][maxn+maxn];
void pfs(int u, int dad) {
f[0][++id] = ii{d[u], u};
firstOrder[u] = id;
euler[id] = u;
for (int v : adj[u])
if (v != dad) {
d[v] = d[u] + 1;
pfs(v, u);
f[0][++id] = ii{d[u], u};
}
}
int lca(int u, int v) {
u = firstOrder[u]; v = firstOrder[v];
if (u > v) swap(u, v);
int k = __lg(v-u+1);
return min(f[k][u], f[k][v-(1<<k)+1]).se;
}
int dis(int u, int v) {
return d[u] + d[v] - 2 * d[lca(u, v)];
}
int cnt[maxn], ans = 0;
multiset<int> s;
void add(int x) {
++cnt[x];
if (cnt[x] > 1) return;
x = firstOrder[x];
auto it = s.insert(x);
if (next(it) != s.end() && it != s.begin()) {
int a = *prev(it), b = *next(it);
ans += dis(euler[x], euler[b]);
ans += dis(euler[x], euler[a]);
ans -= dis(euler[a], euler[b]);
return;
}
if (next(it) != s.end()) {
int y = *next(it);
ans += dis(euler[x], euler[y]);
return;
}
if (it != s.begin()) {
int y = *prev(it);
ans += dis(euler[x], euler[y]);
return;
}
}
void del(int x) {
--cnt[x];
if (cnt[x] > 0) return;
x = firstOrder[x];
auto it = s.find(x);
if (next(it) != s.end() && it != s.begin()) {
int a = *prev(it), b = *next(it);
ans -= dis(euler[x], euler[b]);
ans -= dis(euler[x], euler[a]);
ans += dis(euler[a], euler[b]);
s.erase(it);
return;
}
if (next(it) != s.end()) {
int y = *next(it);
ans -= dis(euler[x], euler[y]);
s.erase(it);
return;
}
if (it != s.begin()) {
int y = *prev(it);
ans -= dis(euler[x], euler[y]);
s.erase(it);
return;
}
}
struct query {
int l, r, idx;
query() {}
query(int _l, int _r, int _idx) : l(_l), r(_r), idx(_idx) {}
bool operator < (const query &other) const {
int u = csk(l), v = csk(other.l);
if (u != v) return u < v;
return r < other.r;
}
} queries[maxn];
int kq[maxn];
int main() {
ios::sync_with_stdio(false);
cin.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);
}
pfs(1, 0);
for (int i = 1; i <= m; i++) cin >> c[i];
for (int i = 1; (1<<i) <= id; i++) for (int j = 1; j + (1<<i) - 1 <= id; j++) f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
for (int i = 1; i <= q; i++) {cin >> queries[i].l >> queries[i].r; queries[i].idx = i;}
sort(queries + 1, queries + q + 1);
int L = 1, R = 0;
for (int o = 1; o <= q; o++) {
auto [l, r, idx] = queries[o];
while (R < r) add(c[++R]);
while (L > l) add(c[--L]);
while (R > r) del(c[R--]);
while (L < l) del(c[L++]);
kq[idx] = ans + dis(euler[*s.begin()], euler[*s.rbegin()]);
}
for (int i = 1; i <= q; i++) cout << kq[i]/2+1 << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |