#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
const int mod=1e9+7,mxn=2e5+5,lg=30,inf=1e18,minf=-1e18;
vector<pii>e,adj[mxn+10];
int hvy[mxn+10],pos[mxn+10],edgenode[mxn+10],h[mxn+10],up[mxn+10][lg+10],sz[mxn+10],hvypa[mxn+10];
int last[mxn+10],mx[mxn+10];
bitset<mxn+10>on;
int n;
void dfs(int cur,int p){
for(auto i:adj[cur]){
if(i.f==p)continue;
edgenode[i.f]=i.s;
h[i.f]=h[cur]+1;
up[i.f][0]=cur;
dfs(i.f,cur);
sz[cur]+=sz[i.f];
}
sz[cur]++;
}
int cnt=1;
void hld(int cur,int p,int phvy){
pos[cur]=cnt++;
hvypa[cur]=phvy;
for(auto i:adj[cur])if(i.f!=p&&sz[hvy[cur]]<sz[i.f])hvy[cur]=i.f;
if(hvy[cur])hld(hvy[cur],cur,phvy);
for(auto i:adj[cur])if(i.f!=p&&i.f!=hvy[cur])hld(i.f,cur,i.f);
}
struct seg{
bool v[2*mxn+10];
void update(int pos,bool val){
pos+=n+1;
v[pos]=val;
for(;pos>0;pos>>=1)v[pos>>1]=(v[pos]&v[pos^1]);
}
bool qry(int l,int r){
bool ans=true;
for(l+=n+1,r+=n+1;l<=r;l>>=1,r>>=1){
if(l&1)ans&=(v[l++]);
if(!(r&1))ans&=(v[r--]);
}
return ans;
}
}t;
struct fen{
int fwk[mxn+10];
void update(int pos,int val){for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;}
int qry(int pos){
int sum=0;
for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
return sum;
}
}f;
void upd(int st,int above,int val){
int cur=st;
while(h[hvypa[cur]]>=h[above]){
f.update(pos[cur]+1,-val);
f.update(pos[hvypa[cur]],val);
if(hvypa[cur]==1)return;
cur=up[hvypa[cur]][0];
}
if(h[cur]<h[above])return;
f.update(pos[cur]+1,-val);
f.update(pos[above],val);
}
int check(int st,int m){
bool ans=true;
int cur=st,tmp;
while(h[hvypa[cur]]>=h[st]-m){
ans&=t.qry(pos[hvypa[cur]],pos[cur]);
tmp=hvypa[cur];
if(hvypa[cur]==1)return (ans==0)?0:hvypa[cur];
cur=up[hvypa[cur]][0];
}
if(h[cur]<h[st]-m){
if(ans)return tmp;
else return 0;
}
int diff=h[cur]-(h[st]-m),above=cur;
for(int i=0;i<=lg;i++)if(diff&(1<<i))above=up[above][i];
ans&=t.qry(pos[above],pos[cur]);
if(ans)return above;
return 0;
}
int findpa(int cur){
int l=0,r=h[cur],ans=minf;
while(l<=r){
int mid=(l+r)/2;
int g=check(cur,mid);
if(g){
l=mid+1;
if(ans==minf||h[ans]>h[g])ans=g;
}
else r=mid-1;
}
return (ans==minf?cur:ans);
}
int ans=minf;
void findans(int cur,int p){
if(!on[cur])ans=max(mx[cur],f.qry(pos[cur]));
else ans=max({ans,mx[cur],f.qry(pos[cur])});
mx[cur]=ans;
for(auto i:adj[cur])if(i.f!=p)findans(i.f,cur);
}
int32_t main(){
fastio
int q,m;cin>>n>>q>>m;
for(int i=1;i<=n-1;i++){
int a,b;cin>>a>>b;
e.pb({a,b});
adj[a].pb({b,i});
adj[b].pb({a,i});
}
dfs(1,-1);
hld(1,-1,1);
for(int i=1;i<=lg;i++)up[1][i]=1;
for(int j=1;j<=lg;j++)for(int i=2;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
f.update(1,1);
while(q--){
int a;cin>>a;
a--;
if(h[e[a].f]<h[e[a].s])a=e[a].s;
else a=e[a].f;
if(on[a]){
int node=up[findpa(a)][0];
last[a]=f.qry(pos[a]);
mx[node]=max(mx[node],f.qry(pos[node]));
mx[a]=max(mx[a],mx[node]);
t.update(pos[a],false);
}
else{
t.update(pos[a],true);
int node=up[findpa(a)][0];
int tmp=f.qry(pos[a])-last[a];
upd(up[a][0],node,tmp);
mx[node]=max(mx[node],mx[node]+(tmp));
}
on[a]=!on[a];
}
findans(1,-1);
for(int i=1;i<=m;i++){
int a;cin>>a;
cout<<mx[a]<<'\n';
}
return 0;
}
Compilation message
synchronization.cpp: In function 'long long int check(long long int, long long int)':
synchronization.cpp:99:16: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | int cur=st,tmp;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14172 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
14428 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
60080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14428 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14428 KB |
Output is correct |
| 6 |
Correct |
5 ms |
16668 KB |
Output is correct |
| 7 |
Correct |
33 ms |
20440 KB |
Output is correct |
| 8 |
Correct |
744 ms |
67780 KB |
Output is correct |
| 9 |
Correct |
767 ms |
67720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
847 ms |
64960 KB |
Output is correct |
| 2 |
Correct |
264 ms |
66828 KB |
Output is correct |
| 3 |
Correct |
256 ms |
66900 KB |
Output is correct |
| 4 |
Correct |
260 ms |
67008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
