/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
const int M_MAX = 100000;
const int Q_MAX = 100000;
const int LOG_N = 17;
int N, M, Q;
vector <int> adj[N_MAX + 2];
int C[M_MAX + 2];
int ql[Q_MAX + 2], qr[Q_MAX + 2];
int parent[N_MAX + 2];
int depth[N_MAX + 2];
int order[N_MAX + 2];
int L[N_MAX + 2], R[N_MAX + 2];
int curr;
int anc[N_MAX + 2][LOG_N];
int ancestor (int u, int k) {
for (int e = 0; e < LOG_N; e++) {
if ((k >> e) & 1) {
u = anc[u][e];
}
}
return u;
}
int lca (int u, int v) {
if (u == 0 || v == 0) {
return 0;
}
if (depth[u] > depth[v]) {
u = ancestor(u, depth[u] - depth[v]);
}
if (depth[v] > depth[u]) {
v = ancestor(v, depth[v] - depth[u]);
}
if (u == v) {
return u;
}
for (int e = LOG_N - 1; e >= 0; e--) {
if (anc[u][e] != anc[v][e]) {
u = anc[u][e];
v = anc[v][e];
}
}
return parent[u];
}
void dfs (int u) {
L[u] = ++curr;
order[curr] = u;
for (int v : adj[u]) {
if (v != parent[u]) {
parent[v] = u;
depth[v] = depth[u] + 1;
dfs(v);
}
}
R[u] = curr;
}
int bucket;
int get_bucket (int i) {
return (i - 1) / bucket + 1;
}
vector <int> queries[N_MAX + 2];
int cnt, root;
int occ[N_MAX + 2];
set <int> S;
void add (int u) {
if (++occ[u] == 1) {
if (S.empty() == true) {
S.insert(L[u]);
cnt = 1; root = u;
return;
}
set <int> :: iterator it = S.insert(L[u]).first;
int ul = (it != S.begin() ? order[*prev(it)] : 0);
int ur = (next(it) != S.end() ? order[*next(it)] : 0);
ul = lca(u, ul);
ur = lca(u, ur);
int v = (depth[ul] > depth[ur] ? ul : ur);
cnt += depth[u] - depth[v];
if (L[v] < L[root]) {
cnt += depth[root] - depth[v];
root = v;
}
}
}
void del (int u) {
if (--occ[u] == 0) {
S.erase(L[u]);
}
}
int answer[Q_MAX + 2];
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> Q;
for (int i = 1; i <= N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= M; i++) {
cin >> C[i];
}
for (int i = 1; i <= Q; i++) {
cin >> ql[i] >> qr[i];
}
depth[1] = 1;
dfs(1);
for (int u = 1; u <= N; u++) {
anc[u][0] = parent[u];
}
for (int e = 1; e < LOG_N; e++) {
for (int u = 1; u <= N; u++) {
anc[u][e] = anc[anc[u][e - 1]][e - 1];
}
}
bucket = max(1, min(N, (int) (N / sqrt(Q))));
for (int i = 1; i <= Q; i++) {
int bl = get_bucket(ql[i]), br = get_bucket(qr[i]);
if (bl < br) {
queries[bl].push_back(i);
} else {
for (int j = ql[i]; j <= qr[i]; j++) {
add(C[j]);
}
answer[i] = cnt;
for (int j = qr[i]; j >= ql[i]; j--) {
del(C[j]);
}
cnt = root = 0;
}
}
for (int b = 1; b <= get_bucket(N); b++) {
sort(queries[b].begin(), queries[b].end(), [&] (const int &i, const int &j) {
return qr[i] < qr[j];
});
int r = b * bucket;
for (int i : queries[b]) {
while (r < qr[i]) {
add(C[++r]);
}
int prv_cnt = cnt, prv_root = root;
for (int j = b * bucket; j >= ql[i]; j--) {
add(C[j]);
}
answer[i] = cnt;
for (int j = ql[i]; j <= b * bucket; j++) {
del(C[j]);
}
cnt = prv_cnt; root = prv_root;
}
while (r > b * bucket) {
del(C[r--]);
}
cnt = root = 0;
}
for (int i = 1; i <= Q; i++) {
cout << answer[i] << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Incorrect |
3 ms |
9308 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Incorrect |
3 ms |
9308 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Incorrect |
2 ms |
9308 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
38 ms |
16656 KB |
Output is correct |
3 |
Incorrect |
52 ms |
16980 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9392 KB |
Output is correct |
2 |
Incorrect |
2 ms |
9308 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Incorrect |
3 ms |
9308 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |