| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1293221 | lto5 | Tourism (JOI23_tourism) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
const int S = 320;
const int L = 18;
const int N = 100005;
int n, m, q;
vector<int> g[N];
int c[N];
int p[N];
int h[N];
int id[N];
int l[N];
int r[N];
int mark[N];
int in[N];
int out[N];
int f[N][L];
int spt[N][L];
int tin[N];
int tout[N];
int s[S];
int blk[N];
int ans[N];
int tree[N];
int tt;
void dfs(int u) {
tin[u] = ++tt;
tree[tt] = u;
for (int i = 0; f[f[u][i]][i]; i++) {
f[u][i + 1] = f[f[u][i]][i];
}
for (int v : g[u]) {
if (v == p[u]) {
continue;
}
p[v] = u;
h[v] = h[u] + 1;
f[v][0] = u;
dfs(v);
}
tout[u] = tt;
}
int lca(int u, int v) {
if (h[u] < h[v]) {
swap(u, v);
}
while (h[u] > h[v]) {
u = f[u][__lg(h[u] - h[v])];
}
if (u == v) {
return u;
}
for (int i = __lg(h[u]); i >= 0; i--) {
if (f[u][i] != f[v][i]) {
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("a.inp", "r", stdin);
// freopen("a", "w", stdout);
#endif // LOCAL
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for (int i = 1; i <= m; i++) {
cin >> c[i];
}
for (int i = 1; i <= q; i++) {
cin >> l[i] >> r[i];
id[i] = i;
}
for (int i = 1; i <= m; i++) {
spt[i][0] = c[i];
}
for (int k = 1; (1 << k) <= m; k++) {
for (int i = 1; i + (1 << k) - 1 <= m; i++) {
spt[i][k] = lca(spt[i][k - 1], spt[i + (1 << (k - 1))][k - 1]);
}
}
auto lca_range = [&](int l, int r) {
int k = __lg(r - l + 1);
return lca(spt[l][k], spt[r - (1 << k) + 1][k]);
};
for (int i = 1; i <= q; i++) {
blk[i] = i / S;
}
sort(id + 1, id + q + 1, [&](int i, int j) {
if (blk[l[i]] != blk[l[j]]) {
return l[i] < l[j];
}
return (blk[l[i]] & 1) ? r[i] < r[j] : r[i] > r[j];
});
int cl = 1, cr = 0;
auto add = [&](int u, int d) {
// cerr << u << " " << d << endl;
while (u) {
s[blk[tin[u]]] -= mark[u] > 0;
// cerr << "vis " << u << " " << p[u] << endl;
mark[u] += d;
// mark[u] = max(mark[u], 0);
s[blk[tin[u]]] += mark[u] > 0;
u = p[u];
}
};
auto get_sum = [&](int l, int r) {
int bl = blk[l];
int br = blk[r];
if (bl == br) {
int ans = 0;
for (int i = l; i <= r; i++) ans += mark[tree[i]] > 0;
return ans;
}
int ans = 0;
for (int i = bl + 1; i <= br - 1; i++) {
ans += s[i];
}
for (int i = l; i < (bl + 1) * S; i++) {
ans += mark[tree[i]] > 0;
}
for (int i = br * S; i <= r; i++) {
ans += mark[tree[i]] > 0;
}
return ans;
};
for (int i = 1; i <= q; i++) {
int L = l[id[i]], R = r[id[i]];
while (cl < L) {
add(c[cl], -1);
cl++;
}
while (cl > L) {
cl--;
add(c[cl], 1);
}
while (cr < R) {
cr++;
add(c[cr], 1);
}
while (cr > R) {
add(c[cr], -1);
cr--;
}
int lc = lca_range(L, R);
// cerr << "----\n";
// for (int u = 1; u <= n; u++) {
// cerr << u << " " << mark[tree[u]] << endl;
// }
ans[id[i]] = get_sum(tin[lc], tout[lc]);
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
}
return 0;
}