#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; #define mid ((left+right)>>1) #include"incursion.h" int n; int par[45023],sub[45023]; pair<int,int>cent; vector<int>komsu[45023]; int tur[45023]; void dfs(int pos,int las){ sub[pos]=1; for(int x:komsu[pos]){ if(x==las)continue; dfs(x,pos); sub[pos]+=sub[x]; } } void dfs(int pos){ for(int x:komsu[pos]){ if(x==par[pos])continue; par[x]=pos; dfs(x); } } vector<int> mark(vector<pair<int,int>>F,int safe){ n=F.size()+1; for(auto&x:F){ komsu[x.fr].pb(x.sc); komsu[x.sc].pb(x.fr); } dfs(1,1); cent.fr=1; while(true){ int nex=-1; for(int x:komsu[cent.fr]){ if(sub[x]>sub[cent.fr])continue; if(sub[x]*2>n){ nex=x; break; } if(sub[x]*2==n){ cent.sc=x; break; } } if(nex==-1)break; cent.fr=nex; } par[cent.fr]=cent.sc; par[cent.sc]=cent.fr; dfs(cent.fr); if(cent.sc)dfs(cent.sc); vector<int>ans(n); for(int i=0;i<n;i++){ ans[i]=1; } int pos=safe; while(pos!=cent.fr&&pos!=cent.sc){ ans[pos-1]=0; pos=par[pos]; } ans[pos-1]=0; return ans; } void locate(vector<pair<int,int>>F,int curr,int t){ n=F.size()+1; for(int i=1;i<=n;i++){ komsu[i].clear(); par[i]=0; cent={0,0}; } for(auto&x:F){ komsu[x.fr].pb(x.sc); komsu[x.sc].pb(x.fr); } dfs(1,1); cent.fr=1; while(true){ int nex=-1; for(int x:komsu[cent.fr]){ if(sub[x]>sub[cent.fr])continue; if(sub[x]*2>n){ nex=x; break; } if(sub[x]*2==n){ cent.sc=x; break; } } if(nex==-1)break; cent.fr=nex; } par[cent.fr]=cent.sc; par[cent.sc]=cent.fr; dfs(cent.fr); if(cent.sc)dfs(cent.sc); int x=t; int pos=curr; for(int i=1;i<=n;i++){ tur[i]=-1; } while(x){ tur[pos]=1; x=visit(par[pos]); pos=par[pos]; } tur[pos]=0; dfs(pos,pos); while(true){ if(tur[pos]==1){ visit(par[pos]); pos=par[pos]; continue; } int nex=-1; for(int x:komsu[pos]){ if(tur[x]!=-1)continue; if(x==par[pos])continue; if(nex==-1||sub[x]>sub[nex])nex=x; } if(nex==-1)return; tur[nex]=visit(nex); pos=nex; } }