#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 7;
const int BASE = 1 << 18;
const int inf = 1e9;
vector<pair<int, int>> G[MAXN];
vector<tuple<int ,int, int, int, pair<int, int>>> accensor[MAXN];
vector<pair<int, int>> edges;
int depth[MAXN];
bool off[MAXN];
int sajz[MAXN];
int parent[MAXN];
int pre[MAXN];
int post[MAXN];
int TREE[BASE << 1];
int vertex[MAXN];
int howaddedge[MAXN];
bool active[MAXN];
int tajm;
int n, q, m;
void dfs_pre(int v, int p, int d = 0){
depth[v] = d;
for(auto [u, id] : G[v]){
if(id == p) continue;
pre[id] = ++tajm;
dfs_pre(u, id, d+1);
}
post[p] = ++tajm;
}
void dfs(int v, int p){
sajz[v] = 1;
parent[v] = p;
for(auto [u, id] : G[v]){
if(off[u] || u == p) continue;
dfs(u, v);
sajz[v] += sajz[u];
}
}
void mark(int v, int p, int centro, int uout, int d, pair<int, int> lca){
accensor[v].push_back({centro, d, p, uout, lca});
for(auto [u, id]: G[v]){
if(off[u] || id == p) continue;
if(depth[u] < depth[v]) mark(u, id, centro, uout, d+1, make_pair(-inf, -inf));
else if(lca.first == -inf) mark(u, id, centro, uout, d+1, make_pair(p, id));
else mark(u, id, centro, uout, d+1, lca);
}
}
int find_centroid(int v, int tree_size){
for(auto [u, id] : G[v]){
if(off[u]) continue;
if(u == parent[v]){
if(tree_size - sajz[v] > tree_size/2) return find_centroid(u, tree_size);
}
else if(sajz[u] > tree_size/2) return find_centroid(u, tree_size);
}
return v;
}
void centroid_decomposition(int V, int tree_size){
if(tree_size == 1) return;
dfs(V, 0);
int centroid = find_centroid(V, tree_size);
off[centroid] = 1;
for(auto [u, id] : G[centroid]){
if(off[u]) continue;
if(depth[u] < depth[centroid]) mark(u, id, centroid, id, 1, make_pair(-inf, -inf));
else mark(u, id, centroid, id, 1, make_pair(inf, inf));
}
for(auto [u, id] : G[centroid]){
if(off[u]) continue;
int new_size = (sajz[u] < sajz[centroid] ? sajz[u]: tree_size - sajz[centroid]);
centroid_decomposition(u, new_size);
}
}
void update(int v, int val){
v += BASE;
TREE[v] = val;
v/=2;
while(v > 0){
int l = 2*v, r = 2*v + 1;
TREE[v] = TREE[l] + TREE[r];
v/=2;
}
}
int query(int a, int b){
if(b < a) swap(a, b);
a += BASE - 1;
b += BASE + 1;
int res = 0;
while(a/2 != b/2){
if(a % 2 == 0) res += TREE[a+1];
if(b % 2 == 1) res += TREE[b-1];
a/=2; b/=2;
}
return res;
}
int ask(int v){
int sum = vertex[v];
for(auto [centroid, d, p, uout, lca] : accensor[v]){
if(lca.first != lca.second){
int tmp = query(pre[lca.first], pre[uout]) + query(pre[lca.second], pre[p]);
if(d == tmp) sum = max(sum, vertex[centroid]);
}
else{
int tmp = query(pre[p], pre[uout]);
if(d == tmp) sum = max(sum, vertex[centroid]);
}
}
return sum;
}
void update_centroid(int v, int val){
vertex[v] = val;
for(auto [centroid, d, p, uout, lca] : accensor[v]){
if(lca.first != lca.second){
int tmp = query(pre[lca.first], pre[uout]) + query(pre[lca.second], pre[p]);
if(d == tmp) vertex[centroid] = max(vertex[centroid], val);
}
else{
int tmp = query(pre[p], pre[uout]);
if(d == tmp) vertex[centroid] = max(vertex[centroid], val);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> m;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
G[a].push_back({b, i});
G[b].push_back({a, i});
edges.push_back({a, b});
vertex[a] = vertex[b] = 1;
}
dfs_pre(1, 0);
centroid_decomposition(1, n);
for(int i = 1; i <= q; i++){
int x;
cin >> x;
if(!active[x]){
auto [a, b] = edges[x-1];
vertex[a] = ask(a);
vertex[b] = ask(b);
int tmp = howaddedge[x];
howaddedge[x] = vertex[a] + vertex[b] - howaddedge[x];
update(pre[x], 1);
update(post[x], -1);
if(tmp < howaddedge[x]){
update_centroid(a, howaddedge[x]);
update_centroid(b, howaddedge[x]);
}
}
else{
auto [a, b] = edges[x-1];
vertex[a] = ask(a);
vertex[b] = ask(b);
howaddedge[x] = max(vertex[a], vertex[b]);
update(pre[x], 0);
update(post[x], 0);
}
active[x] ^= 1;
}
for(int i = 1; i <= m; i++){
int x;
cin >> x;
cout << ask(x) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
5020 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
40776 KB |
Output is correct |
| 2 |
Correct |
326 ms |
40292 KB |
Output is correct |
| 3 |
Incorrect |
491 ms |
61068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1321 ms |
61308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
