#include <bits/stdc++.h>
using namespace std;
vector<int> a[100001], tr[800001];
int depth[100001], state[100001], cnt[100001], f[100001], mx[100001], p[100001], r[100001];
pair<int, int> edge[100001];
vector<pair<int, int>> change;
int find(int x){
if(p[x]==x){
return x;
}else return find(p[x]);
}
void unite(int u, int v){
int ru = find(u), rv = find(v);
if(ru!=rv){
change.push_back({ru, rv});
int tmp = mx[ru] + mx[rv] - f[v];
mx[ru] = mx[rv] = tmp;
if(r[ru] > r[rv]){
p[rv] = ru;
r[ru] += r[rv];
}else{
p[ru] = rv;
r[rv] += r[ru];
}
}
}
void undo(){
auto [u, v] = change.back();
change.pop_back();
int tmp = max(mx[u], mx[v]);
mx[u] = mx[v] = tmp;
if(r[u] > r[v]){
r[u]-=r[v];
}else r[v]-=r[u];
p[u] = u;
p[v] = v;
}
void dfs(int u, int p){
for (int v:a[u]){
if(v!=p){
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
}
void add(int node, int start, int end, int l, int r, int id){
if(start > r or end < l){
return;
}
if(l<=start and end<=r){
tr[node].push_back(id);
return;
}
int mid = (start+end)/2;
add(2*node, start, mid, l, r, id);
add(2*node+1, mid+1, end, l, r, id);
}
void query(int node, int start, int end){
for (int id:tr[node]){
auto [u, v] = edge[id];
if(depth[u] > depth[v])swap(u, v);
unite(u, v);
}
if(start!=end){
int mid = (start+end)/2;
query(2*node, start, mid);
query(2*node+1, mid+1, end);
}
for (int id:tr[node]){
auto [u,v] = edge[id];
if(depth[u] > depth[v])swap(u,v);
f[v] = mx[find(v)];
undo();
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i =1;i<n;++i){
int u, v;
cin >> u >> v;
edge[i] = {u, v};
a[u].push_back(v);
a[v].push_back(u);
}
for (int i =1;i<=n;++i){
mx[i] = 1;
r[i] = 1, p[i] = i;
}
dfs(1, 0);
for (int i = 1;i<=m;++i){
int id;
cin >> id;
if(state[id]==0){
state[id] = i;
}else{
add(1, 1, m, state[id], i-1, id);
state[id] = 0;
}
}
for (int i = 1;i<n;++i){
if(state[i]){
add(1, 1, m, state[i], m, i);
state[i] = 0;
}
}
query(1, 1, m);
while(q--){
int u;
cin >> u;
cout << mx[find(u)] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |