#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int MAXN = 200005;
int n, m, q, k, u, v, lg;
int tin[MAXN], tout[MAXN], val[MAXN], dst[MAXN], timer = 0;
int up[MAXN][25], a[MAXN], num[MAXN], ans[MAXN];
pair<pair<int, int>, int> query[MAXN];
vector<int> adj[MAXN];
set<int> active;
int sz = 0;
void dfs(int x, int p, int depth) {
tin[x] = timer++;
val[tin[x]] = x;
dst[x] = depth;
up[x][0] = p;
for (int i = 1; i <= lg; ++i)
up[x][i] = up[up[x][i - 1]][i - 1];
for (int neighbor : adj[x]) {
if (neighbor != p) {
dfs(neighbor, x, depth + 1);
}
}
tout[x] = timer++;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = lg; i >= 0; --i) {
if (!is_ancestor(up[u][i], v)) {
u = up[u][i];
}
}
return up[u][0];
}
inline int dist(int x, int y) {
return dst[x] + dst[y] - 2 * dst[lca(x, y)];
}
inline void add(int x) {
num[x]++;
if (num[x] > 1) return;
if (active.empty()) {
active.insert(tin[x]);
return;
}
auto it = active.insert(tin[x]).first;
auto prev = it == active.begin() ? --active.end() : prev(it);
auto next = next(it) == active.end() ? active.begin() : next(it);
sz += dist(val[*prev], val[*it]) + dist(val[*it], val[*next]) - dist(val[*prev], val[*next]);
}
inline void remove(int x) {
num[x]--;
if (num[x] > 0) return;
auto it = active.find(tin[x]);
auto prev = it == active.begin() ? --active.end() : prev(it);
auto next = next(it) == active.end() ? active.begin() : next(it);
sz -= dist(val[*prev], val[*it]) + dist(val[*it], val[*next]) - dist(val[*prev], val[*next]);
active.erase(it);
}
bool compare_queries(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
int block_a = a.ff.ff / k, block_b = b.ff.ff / k;
if (block_a != block_b) return block_a < block_b;
return block_a % 2 ? a.ff.ss > b.ff.ss : a.ff.ss < b.ff.ss;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
lg = ceil(log2(n));
k = ceil(sqrt(m));
for (int i = 1; i < n; i++) {
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
for (int i = 1; i <= q; i++) {
cin >> query[i].ff.ff >> query[i].ff.ss;
query[i].ss = i;
}
dfs(1, 1, 0);
sort(query + 1, query + q + 1, compare_queries);
int tl = 1, tr = 1;
add(a[tl]);
for (int i = 1; i <= q; i++) {
int l = query[i].ff.ff, r = query[i].ff.ss;
while (tr < r) add(a[++tr]);
while (tl > l) add(a[--tl]);
while (tr > r) remove(a[tr--]);
while (tl < l) remove(a[tl++]);
ans[query[i].ss] = (sz / 2) + 1;
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << " ";
}
}
Compilation message
tourism.cpp: In function 'void add(int)':
tourism.cpp:60:57: error: use of 'prev' before deduction of 'auto'
60 | auto prev = it == active.begin() ? --active.end() : prev(it);
| ^~~~
tourism.cpp:61:17: error: use of 'next' before deduction of 'auto'
61 | auto next = next(it) == active.end() ? active.begin() : next(it);
| ^~~~
tourism.cpp:61:61: error: use of 'next' before deduction of 'auto'
61 | auto next = next(it) == active.end() ? active.begin() : next(it);
| ^~~~
tourism.cpp: In function 'void remove(int)':
tourism.cpp:71:57: error: use of 'prev' before deduction of 'auto'
71 | auto prev = it == active.begin() ? --active.end() : prev(it);
| ^~~~
tourism.cpp:72:17: error: use of 'next' before deduction of 'auto'
72 | auto next = next(it) == active.end() ? active.begin() : next(it);
| ^~~~
tourism.cpp:72:61: error: use of 'next' before deduction of 'auto'
72 | auto next = next(it) == active.end() ? active.begin() : next(it);
| ^~~~
