#include<bits/stdc++.h>
using namespace std;
const int n_max = 1e5 + 7;
const int base = 131072;
// const int base = 4;
const int max_log = 20;
int activated[n_max];
vector<int> graph[n_max];
pair<int, int> array_lines[n_max];
int jump[max_log + 2][n_max];
int date[n_max];
int common_date[n_max];
int lvl[n_max];
pair<int, int> range[n_max];
int tree[base*2];
void add(int a, int b, int vallue, int v = 1, int l = 0, int r = base - 1){
if(a <= l and b >= r){
tree[v] += vallue;
return;
}
if(b < l or a > r){
return;
}
int mid = (l+r)/2;
add(a, b, vallue, v * 2, l, mid);
add(a, b, vallue, v * 2 + 1, mid + 1, r);
}
int get_line(int v){
if(v == 0){
return 0;
}
return (get_line(v/2) + tree[v]);
}
int find(int v){
int number = (1<<(max_log-1));
for(int i = max_log - 1; i >= 0; i--){
int line_v = get_line(range[v].first + base);
int line_v_jump = get_line(range[jump[i][v]].first + base);
if(lvl[v] - line_v == lvl[jump[i][v]] - line_v_jump){
v = jump[i][v];
}
number /= 2;
}
return v;
}
void activate(pair<int, int> actual_line){
int upper_point, lower_point;
if(lvl[actual_line.first] < lvl[actual_line.second]){
upper_point = actual_line.first;
lower_point = actual_line.second;
}else{
upper_point = actual_line.second;
lower_point = actual_line.first;
}
upper_point = find(upper_point);
date[upper_point] = date[upper_point] + date[lower_point] - common_date[lower_point];
add(range[lower_point].first, range[lower_point].second, 1);
}
void deactivate(pair<int, int> actual_line){
int upper_point, lower_point;
if(lvl[actual_line.first] < lvl[actual_line.second]){
upper_point = actual_line.first;
lower_point = actual_line.second;
}else{
upper_point = actual_line.second;
lower_point = actual_line.first;
}
upper_point = find(upper_point);
common_date[lower_point] = date[upper_point];
date[lower_point] = date[upper_point];
add(range[lower_point].first, range[lower_point].second, -1);
}
int DFS(int v, int p, int deep, int nr){
lvl[v] = deep;
range[v].first = nr;
jump[0][v] = p;
for(auto u: graph[v]){
if(u != p){
nr = DFS(u, v, deep + 1, nr + 1);
}
}
range[v].second = nr;
return nr;
}
void init(int n){
DFS(1, 0, 1, 1);
for(int i = 1; i < max_log; i++){
for(int j = 0; j <= n; j++){
jump[i][j] = jump[i-1][jump[i-1][j]];
}
}
for(int i = 1; i <= n; i++){
date[i] = 1;
}
}
void print(int n){
cout << "\nSYSTEM OUTPUT\n";
for(int i = 0; i <= n; i++){
cout << i << " " << lvl[i] << " " << range[i].first << ' ' << range[i].second << " " << date[i] << " " << date[find(i)] << '\n';
}
}
void print_inner(int n){
cout << "\nSYSTEM OUTPUT (INNER)\n";
for(int i = 0; i <= n; i++){
cout << i << " " << date[i] << " " << find(i) << " " << date[find(i)] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
array_lines[i] = {a, b};
}
init(n);
for(int i = 0; i < m; i++){
int line;
cin >> line;
if(activated[line] == 0){
activate(array_lines[line]);
activated[line] = 1;
}else{
deactivate(array_lines[line]);
activated[line] = 0;
}
//print_inner(n);
}
for(int i = 0; i < q; i++){
int v;
cin >> v;
v = find(v);
cout << date[v] << '\n';
}
//print(n);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14988 KB |
Output is correct |
| 6 |
Correct |
5 ms |
14940 KB |
Output is correct |
| 7 |
Correct |
32 ms |
15452 KB |
Output is correct |
| 8 |
Correct |
31 ms |
15452 KB |
Output is correct |
| 9 |
Correct |
31 ms |
15452 KB |
Output is correct |
| 10 |
Correct |
508 ms |
20980 KB |
Output is correct |
| 11 |
Correct |
339 ms |
20608 KB |
Output is correct |
| 12 |
Correct |
353 ms |
26968 KB |
Output is correct |
| 13 |
Correct |
293 ms |
20460 KB |
Output is correct |
| 14 |
Correct |
181 ms |
20312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
253 ms |
23684 KB |
Output is correct |
| 2 |
Correct |
254 ms |
23632 KB |
Output is correct |
| 3 |
Correct |
145 ms |
26452 KB |
Output is correct |
| 4 |
Correct |
150 ms |
26212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14940 KB |
Output is correct |
| 7 |
Correct |
42 ms |
16220 KB |
Output is correct |
| 8 |
Correct |
504 ms |
27860 KB |
Output is correct |
| 9 |
Correct |
570 ms |
27984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
472 ms |
27472 KB |
Output is correct |
| 2 |
Correct |
256 ms |
27388 KB |
Output is correct |
| 3 |
Correct |
249 ms |
27480 KB |
Output is correct |
| 4 |
Correct |
257 ms |
27476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14936 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 5 |
Correct |
6 ms |
14940 KB |
Output is correct |
| 6 |
Correct |
43 ms |
15656 KB |
Output is correct |
| 7 |
Correct |
464 ms |
21904 KB |
Output is correct |
| 8 |
Correct |
465 ms |
27692 KB |
Output is correct |
| 9 |
Correct |
378 ms |
21568 KB |
Output is correct |
| 10 |
Correct |
304 ms |
21504 KB |
Output is correct |
| 11 |
Correct |
381 ms |
24764 KB |
Output is correct |
| 12 |
Correct |
370 ms |
24732 KB |
Output is correct |
| 13 |
Correct |
248 ms |
27380 KB |
Output is correct |
