[[Centroid Decomposition]]
link
Build the centroid tree
Precalculate the distances from the centroids to every node in their subtrees, for adding marked nodes.
Then, by this way to anwser the queries.
![[Pasted image 20220607165507.png]]
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
const int N=200005,inf=1061109567;
struct G{
vector<int>_[N];
void add(int u,int v){
_[u].push_back(v);
_[v].push_back(u);
}
}ori;
struct da{
int to,id,dis;
};
int to,id,dis;
vector<da>pa[N];//path
vector<int>br[N];//branch
int mi[N][2];
bool f[N];
int sz[N];
int getsz(int u,int p=0){
sz[u]=1;for(auto v:ori._[u])if(v!=p&&!f[v])sz[u]+=getsz(v,u);
return sz[u];
}
int tot;
int find(int u,int p=0){
for(auto v:ori._[u])if(v!=p&&!f[v]&&sz[v]*2>tot)return find(v,u);
return u;
}
void dfs(int u,int p=0){
dis++;
for(auto v:ori._[u])
if(v!=p&&!f[v])
dfs(v,u);
pa[u].push_back({to,id,dis});
dis--;
}
void centroid(int u=1){
tot=getsz(u),u=find(u);
br[u].push_back(inf);//id从1开始
f[u]=1;
for(auto v:ori._[u])if(!f[v]){
centroid(v);
to=u,id=br[u].size(),dis=0;
dfs(v);
br[u].push_back(inf);
}
f[u]=0;
}
int ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)scanf("%d%d",&a,&b),ori.add(a,b);
centroid();
for(int i=0,opt=1,x=1;i<=m;i++){
if(opt==1){
mi[x][0]=mi[x][1]=br[x][0]=0;
for(auto v:pa[x]){to=v.to,id=v.id,dis=v.dis;
br[to][id]=min(br[to][id],dis);
for(int o=0;o<=1;o++)
if(br[to][id]<br[to][mi[to][o]])
swap(id,mi[to][o]);
}
}
else{
ans=br[x][mi[x][0]];
for(auto v:pa[x]){to=v.to,id=v.id,dis=v.dis;
ans=min(ans,br[to][mi[to][id==mi[to][0]]]+dis);
}
printf("%d\n",ans);
}
if(i!=m)scanf("%d%d",&opt,&x);
}
}