#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 4e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
struct SegmentTree {
int tree[2 * MAXN];
void insert (int x) {
tree[x]++;
}
void erase (int x) {
tree[x]--;
}
int left (int x) {
for (int i = x; i >= 1; i--) if (tree[i]) return i;
return -1;
}
int right (int x) {
for (int i = x + 1; i < 2 * MAXN; i++) if (tree[i]) return i;
return -1;
}
bool empty (int x) {
bool flag = 0; for (int i = 1; i < 2 * MAXN; i++) flag |= tree[i];
return !flag;
}
/* void add (int l, int r, int a, int node) {
if (l == r) {
tree[node] = 1; return;
}
if (a <= mid) add(l, mid, a, tl);
else add(mid + 1, r, a, tr);
tree[node] = tree[tl] | tree[tr];
}
void rem (int l, int r, int a, int node) {
if (l == r) {
tree[node] = 0; return;
}
if (a <= mid) rem(l, mid, a, tl);
else rem(mid + 1, r, a, tr);
tree[node] = tree[tl] | tree[tr];
}
int get1 (int l, int r, int a, int node) {
if (!tree[node] || r < a) return -1;
if (l == r) return l;
int x = get1(l, mid, a, tl);
if (x != -1 && x >= a) return x;
return get1(mid + 1, r, a, tr);
}
int get2 (int l, int r, int a, int node) {
if (!tree[node] || l > a) return -1;
if (l == r) return l;
int x = get2(mid + 1, r, a, tr);
if (x != -1 && x <= a) return x;
return get2(l, mid, a, tl);
}
void insert (int x) {
add(1, MAXN, x, 1);
}
void erase (int x) {
rem(1, MAXN, x, 1);
}
int left (int x) {
if (x == 1) return -1;
return get2(1, MAXN, x - 1, 1);
}
int right (int x) {
if (x == MAXN) return -1;
return get1(1, MAXN, x + 1, 1);
}
bool empty () {
return tree[1] == 0;
}*/
} dd;
int in[MAXN], depth[MAXN], revin[MAXN];
pair <int, int> sparse[__lg(MAXN)][MAXN];
vector <int> adj[MAXN];
int n, m, q;
int cnt = 0;
void dfs (int pos, int par, int dep = 1) {
depth[pos] = dep;
sparse[0][++cnt] = {dep, pos};
in[pos] = cnt; revin[cnt] = pos;
for (auto j : adj[pos]) {
if (j != par) {
dfs(j, pos, dep + 1);
sparse[0][++cnt] = {dep, pos};
}
}
}
int sparse2[__lg(MAXN)][MAXN];
int query (int l, int r) {
if (l > r) swap(l, r);
int x = __lg(r - l + 1);
return min(sparse[x][l], sparse[x][r - (1 << x) + 1]).second;
}
int query2 (int l, int r) {
int x = __lg(r - l + 1);
return query(in[sparse2[x][l]], in[sparse2[x][r - (1 << x) + 1]]);
}
int arr[MAXN];
array <int, 3> queries[MAXN];
int ret[MAXN];
int ans = 0;
void add (int x) {
ans += depth[x];
int l = dd.left(in[x]), r = dd.right(in[x]);
if (r != -1) ans -= depth[query(in[x], r)];
if (l != -1) ans -= depth[query(l, in[x])];
if (l != -1 && r != -1) ans += depth[query(l, r)];
dd.insert(in[x]);
}
void rem (int x) {
dd.erase(in[x]);
ans -= depth[x];
int l = dd.left(in[x]), r = dd.right(in[x]);
if (r != -1) ans += depth[query(in[x], r)];
if (l != -1) ans += depth[query(l, in[x])];
if (l != -1 && r != -1) ans -= depth[query(l, r)];
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, -1);
for (int i = 1; i <= __lg(cnt); i++) {
for (int j = 1; j + (1 << i) - 1 <= cnt; j++) {
sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
}
}
for (int i = 1; i <= m; i++) {
cin >> arr[i];
sparse2[0][i] = arr[i];
}
for (int i = 1; i <= __lg(m); i++) {
for (int j = 1; j + (1 << i) - 1 <= m; j++) {
sparse2[i][j] = query(in[sparse2[i - 1][j]], in[sparse2[i - 1][j + (1 << (i - 1))]]);
}
}
/*for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
vector <int> g;
for (int j = l; j <= r; j++) g.push_back(arr[j]);
sort(g.begin(), g.end(), [&] (int a, int b) {
return in[a] < in[b];
});
int ans = depth[g[0]], lca = g[0];
for (int j = 1; j < (int)g.size(); j++) {
ans += depth[g[j]] - depth[query(in[g[j]], in[g[j - 1]])];
lca = query(in[lca], in[g[j]]);
}
ans -= depth[lca]; ans++;
cout << ans << '\n';
}*/
for (int i = 1; i <= q; i++) {
cin >> queries[i][0] >> queries[i][1]; queries[i][2] = i;
}
int x = sqrt(m); while (x * x < m) x++; while (x * x > m) x--;
sort(queries + 1, queries + q + 1, [&] (array <int, 3> &a, array <int, 3> &b) {
return a[0] / x == b[0] / x ? a[1] < b[1] : a[0] / x < b[0] / x;
});
int l = queries[1][0], r = queries[1][1];
for (int i = l; i <= r; i++) add(arr[i]);
ret[queries[1][2]] = ans - depth[query2(l, r)] + 1;
for (int i = 2; i <= q; i++) {
int tll = queries[i][0], trr = queries[i][1];
// while (l < tll) rem(arr[l++]);
// while (l > tll) add(arr[--l]);
//// while (r < trr) add(arr[++r]);
// while (r > trr) rem(arr[r--]);
memset(dd.tree, 0, sizeof(dd.tree)); ans = 0;
for (int j = tll; j <= trr; j++) add(arr[j]);
bool flag = 1; for (int j = tll + 1; j <= trr; j++) flag &= arr[j] == arr[j - 1];
ret[queries[i][2]] = ans - depth[query2(l, r)] + 1;
}
for (int i = 1; i <= q; i++) cout << ret[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
37980 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
40028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
37980 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
40028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
40028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
37872 KB |
Output is correct |
| 2 |
Incorrect |
2109 ms |
101392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
37976 KB |
Output is correct |
| 2 |
Execution timed out |
5099 ms |
40028 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
37980 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
40028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
