#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const int L = 19;
int n, m, q, st[N], en[N], depth[N], tt = 0;
vector<int> adj[N];
vector<int> lca_et;
int sparse[2 * N][L], st_lca[N], en_lca[N];
int dep_min(int a, int b) {
return depth[a] < depth[b] ? a : b;
}
void build_rmq() {
int k = sz(lca_et);
for (int i = 0; i < k; i++) sparse[i][0] = lca_et[i];
for (int c = 2, l = 1; c <= k; c *= 2, l++) {
for (int i = 0; i + c <= k; i++) {
sparse[i][l] = dep_min(sparse[i][l-1], sparse[i + c/2][l-1]);
}
}
}
int rmq_qry(int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
int len = 1 << lg;
return dep_min(sparse[l][lg], sparse[r - len + 1][lg]);
}
int lca(int a, int b) {
if (st_lca[a] > st_lca[b]) swap(a, b);
return rmq_qry(st_lca[a], en_lca[b]);
}
void dfs(int c, int p) {
if (p != -1) depth[c] = depth[p] + 1;
st[c] = tt++;
st_lca[c] = en_lca[c] = sz(lca_et);
lca_et.push_back(c);
for (int nxt : adj[c]) if (nxt != p) {
dfs(nxt, c);
en_lca[c] = sz(lca_et);
lca_et.push_back(c);
}
en[c] = tt-1;
}
int ans[N], c[N], lca_l[N], lca_r[N];
int rev[N], par[N], w[N];
pair<int, int> range[N];
vector<int> aux[N];
vector<pair<int, int>> ev[N];
void dfs_aux_range(int c) {
for (int nxt : aux[c]) {
dfs_aux_range(nxt);
range[c].first = max(range[c].first, range[nxt].first);
range[c].second = min(range[c].second, range[nxt].second);
}
}
void rec(int l, int r, vector<ar<int, 3>> qs) {
if (!sz(qs)) return;
if (r <= l) return;
int m = (l + r) / 2; // [l..m], [m+1..r]
vector<ar<int, 3>> one, two, mine;
for (auto qi : qs) {
if (qi[1] <= m)
one.push_back(qi);
else if (qi[0] > m)
two.push_back(qi);
else
mine.push_back(qi);
}
rec(l, m, one), rec(m+1, r, two);
vector<int> use;
for (int i = l; i <= r; i++) use.push_back(c[i]);
sort(use.begin(), use.end(), [&](int x, int y) {
return st[x] < st[y];
});
use.resize(unique(use.begin(), use.end()) - use.begin());
int base = sz(use);
for (int i = 0; i < base; i++) {
use.push_back(lca(use[i], use[(i+1) % base]));
}
sort(use.begin(), use.end(), [&](int x, int y) {
return st[x] < st[y];
});
use.resize(unique(use.begin(), use.end()) - use.begin());
for (int i = 0; i < sz(use); i++) {
rev[use[i]] = i;
aux[i].clear();
}
for (int i = 1; i < sz(use); i++) {
par[i] = rev[lca(use[i-1], use[i])];
aux[par[i]].push_back(i);
w[i] = depth[use[i]] - depth[use[par[i]]];
}
int k = sz(use);
// max index of something on the left, min index of something on the right
for (int i = 0; i < k; i++) {
range[i] = {-1, MOD};
}
for (int i = l; i <= m; i++) {
int cur = rev[c[i]];
range[cur].first = max(range[cur].first, i);
}
for (int i = m+1; i <= r; i++) {
int cur = rev[c[i]];
range[cur].second = min(range[cur].second, i);
}
dfs_aux_range(0);
for (int i = m; i >= l; i--) {
lca_l[i] = c[i];
if (i < m) lca_l[i] = lca(lca_l[i], lca_l[i+1]);
}
for (int i = m+1; i <= r; i++) {
lca_r[i] = c[i];
if (i > m+1) lca_r[i] = lca(lca_r[i], lca_r[i-1]);
}
int sum = 0;
for (int j = 1; j < k; j++) sum += w[j];
int top = use[0];
for (int i = l; i <= r; i++) ev[i].clear();
vector<int> data(r - l + 1);
auto add = [&](int L, int R, int x) {
if (R < L) return;
L -= l;
R -= l;
for (int i = L; i <= R; i++) data[i] += x;
};
auto qry = [&](int i) {
return data[i - l];
};
for (auto [L, R, i] : mine) {
ans[i] += sum;
ans[i] -= depth[lca(lca_l[L], lca_r[R])] - depth[top];
ev[L].push_back({R, i});
/*
for (int j = 1; j < k; j++) {
if (range[j].first < L && R < range[j].second) {
ans[i] -= w[j];
}
}
*/
}
for (int j = 1; j < k; j++) {
ev[range[j].first].push_back({range[j].second, -w[j]});
}
for (int i = l; i <= r; i++) {
for (auto [R, x] : ev[i]) {
if (x >= 0) {
ans[x] += qry(R);
} else {
x *= -1;
add(l, min(r, R-1), -x);
}
}
}
}
void solve() {
cin >> n >> m >> q;
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b, --a, --b;
adj[a].push_back(b), adj[b].push_back(a);
}
dfs(0, -1);
build_rmq();
for (int i = 0; i < m; i++) {
cin >> c[i], --c[i];
}
vector<ar<int, 3>> qs(q);
for (int i = 0; i < q; i++) {
int l, r; cin >> l >> r, --l, --r;
qs[i] = {l, r, i};
}
rec(0, m-1, qs);
for (int i = 0; i < q; i++) cout << ans[i]+1 << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Incorrect |
2423 ms |
39136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
1536 ms |
29256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 4 |
Incorrect |
3689 ms |
35940 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
