#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct SegmentTree {
int n;
vector<int> sum;
SegmentTree(int n) : n(n) {
sum.assign(4 * n, 0);
}
void update(int i, int v) {
update(i, v, 0, 0, n - 1);
}
void update(int i, int v, int x, int lx, int rx) {
if (lx == rx) {
sum[x] += v;
return;
}
int mid = (lx + rx) / 2;
if (i <= mid) {
update(i, v, 2 * x + 1, lx, mid);
} else {
update(i, v, 2 * x + 2, mid + 1, rx);
}
sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
}
int get(int l, int r) {
return get(l, r, 0, 0, n - 1);
}
int get(int l, int r, int x, int lx, int rx) {
if (lx > r || rx < l) return 0;
if (l <= lx && rx <= r) return sum[x];
int mid = (lx + rx) / 2;
return get(l, r, 2 * x + 1, lx, mid) + get(l, r, 2 * x + 2, mid + 1, rx);
}
};
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> c(m);
vector<vector<int>> indices(n);
for (int i = 0; i < m; ++i) {
cin >> c[i];
--c[i];
indices[c[i]].push_back(i);
}
vector<int> l(q), r(q);
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i];
--l[i], --r[i];
}
vector<int> dep(n), sz(n);
function<void(int, int)> calc = [&](int u, int p) {
for (int i = 0; i < adj[u].size(); ++i) {
if (adj[u][i] == p) {
swap(adj[u][i], adj[u].back());
adj[u].pop_back();
break;
}
}
sz[u] = 1;
for (auto v : adj[u]) {
dep[v] = dep[u] + 1;
calc(v, u);
sz[u] += sz[v];
}
for (int i = 1; i < adj[u].size(); ++i) {
if (sz[adj[u][i]] > sz[adj[u][0]]) {
swap(adj[u][i], adj[u][0]);
}
}
};
calc(0, -1);
vector<set<array<int, 4>>> st(n);
vector<vector<pair<int, int>>> update(m);
auto addRange = [&](int l, int r, int v) {
if (l > r) return;
update[l].push_back({l, v});
if (r + 1 < m) {
update[r + 1].push_back({l, -v});
}
};
int const inf = 1e9;
auto append = [&](int u, int l, int r) {
auto it = prev(st[u].upper_bound(array{l, r, inf, inf}));
auto [L, R, d, t] = *it;
addRange(L, R, d - dep[u] + 1);
if (L == l && r == R && l > 0 && r < m - 1) {
auto itL = prev(it);
auto itR = next(it);
auto [cl, cr, cd, ct] = *itL;
addRange(cl, cr, cd - dep[u] + 1);
auto [cl, cr, cd, ct] = *itR;
addRange(cl, cr, cd - dep[u] + 1);
int nl = (*itL)[0], nr = (*itR)[1];
st[u].erase(it);
st[u].erase(itL);
st[u].erase(itR);
st[u].insert(array{nl, nr, dep[u] - 1, 1});
} else if (L == l && l > 0) {
auto itL = prev(it);
auto [cl, cr, cd, ct] = *itL;
addRange(cl, cr, cd - dep[u] + 1);
int nl = cl, nr = r;
st[u].erase(it);
st[u].erase(itL);
st[u].insert(array{nl, nr, dep[u] - 1, 1});
if (r < R) {
st[u].insert(array{r + 1, R, dep[u] - 1, 0});
}
} else if (r == R && r + 1 < m - 1) {
auto itR = next(it);
auto [cl, cr, cd, ct] = *itR;
addRange(cl, cr, cd - dep[u] + 1);
int nl = l, nr = cr;
st[u].erase(it);
st[u].erase(itR);
st[u].insert(array{nl, nr, dep[u] - 1, 1});
if (L < l) {
st[u].insert(array{L, l - 1, dep[u] - 1, 0});
}
} else {
st[u].erase(it);
st[u].insert(array{l, r, dep[u] - 1, 1});
if (L < l) {
st[u].insert(array{L, l - 1, dep[u] - 1, 0});
}
if (r < R) {
st[u].insert(array{r + 1, R, dep[u] - 1, 0});
}
}
};
function<void(int)> dfs = [&](int u) {
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
dfs(v);
if (i == 0) {
swap(st[u], st[v]);
} else {
for (auto [l, r, d, t] : st[v]) {
addRange(l, r, d - dep[v] + 1);
if (t == 1) {
append(u, l, r);
}
}
}
}
for (auto i : indices[u]) {
append(u, i, i);
}
if (st[u].size() == 0) {
st[u] = {array{0, m - 1, dep[u], 0}};
}
};
dfs(0);
for (auto [l, r, d, t] : st[0]) {
addRange(l, r, d - dep[0] + 1);
}
vector<vector<int>> query(m);
for (int i = 0; i < q; ++i) {
query[r[i]].push_back(i);
}
vector<int> ans(q);
SegmentTree seg(m);
for (int i = 0; i < m; ++i) {
for (auto [j, v] : update[i]) {
seg.update(j, v);
}
for (auto j : query[i]) {
ans[j] = n - seg.get(0, l[j]);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Compilation message
tourism.cpp: In lambda function:
tourism.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < adj[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
tourism.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 1; i < adj[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
tourism.cpp: In lambda function:
tourism.cpp:113:19: error: conflicting declaration 'auto cl'
113 | auto [cl, cr, cd, ct] = *itR;
| ^~
tourism.cpp:111:19: note: previous declaration as 'std::tuple_element<0, std::array<int, 4> >::type&& cl'
111 | auto [cl, cr, cd, ct] = *itL;
| ^~
tourism.cpp:113:23: error: conflicting declaration 'auto cr'
113 | auto [cl, cr, cd, ct] = *itR;
| ^~
tourism.cpp:111:23: note: previous declaration as 'std::tuple_element<1, std::array<int, 4> >::type&& cr'
111 | auto [cl, cr, cd, ct] = *itL;
| ^~
tourism.cpp:113:27: error: conflicting declaration 'auto cd'
113 | auto [cl, cr, cd, ct] = *itR;
| ^~
tourism.cpp:111:27: note: previous declaration as 'std::tuple_element<2, std::array<int, 4> >::type&& cd'
111 | auto [cl, cr, cd, ct] = *itL;
| ^~
tourism.cpp:113:31: error: conflicting declaration 'auto ct'
113 | auto [cl, cr, cd, ct] = *itR;
| ^~
tourism.cpp:111:31: note: previous declaration as 'std::tuple_element<3, std::array<int, 4> >::type&& ct'
111 | auto [cl, cr, cd, ct] = *itL;
| ^~
tourism.cpp:113:18: warning: unused structured binding declaration [-Wunused-variable]
113 | auto [cl, cr, cd, ct] = *itR;
| ^~~~~~~~~~~~~~~~
tourism.cpp: In lambda function:
tourism.cpp:155:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for (int i = 0; i < adj[u].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
