题目传送门
题意分析
看到题目，先打暴力。
暴力有两种写法：
- 修改 \(\mathcal O(1)\)，查询就 \(\mathcal O(n)\) 枚举红色点计算路径长度。
- 修改 \(\mathcal O(n)\)，BFS 更新每个点到红色点的距离；查询 \(\mathcal O(1)\)。
由于 \(2\leq n\leq10^5\)，不可通过。
基于复杂平衡思想，我们想要把他们拼到一起，平衡一下复杂度。但是这两种方法几乎毫不相干，考虑对操作分块。
操作离线下来，每 \(B\) 个一组。
- 考虑每隔 \(B\) 个块就重构每个点到红色点的距离，这个可以优化写法二，多源 BFS 做到 \(\mathcal O(n)\) 重构。
- 之后块内操作可以写法一，因为只会存在 \(B\) 个新增的红色点，所以只需要 \(\mathcal O(B)\) 枚举红色点，再与重构得到的答案取 \(\min\) 即可查询；修改 \(\mathcal O(1)\)。
总时间复杂度 \(\mathcal O\left(\dfrac{nm}B+mB\right)\)，取 \(B=\sqrt n\) 得到最优复杂度 \(\mathcal O\left(m\sqrt n\right)\)。
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5,inf=0x3f3f3f3f;
int n,m,B,dis[N+1];
vector<int>g[N+1];
bool vis[N+1];
vector<int>node;
void bfs(){memset(dis,0x3f,sizeof(dis));queue<int>q;for(int i=1;i<=n;i++){if(vis[i]){dis[i]=0;q.push(i);}}while(q.size()){int x=q.front();q.pop();for(int v:g[x]){if(dis[v]!=inf){continue;}dis[v]=dis[x]+1;q.push(v);}}
}
void build(){for(int x:node){vis[x]=true;}node.resize(0);bfs();
}
int father[N+1],depth[N+1],dfn[N+1],rnk[N+1];
void dfs(int x,int fx){father[x]=fx;depth[x]=depth[fx]+1;static int cnt;dfn[x]=++cnt;rnk[cnt]=x;for(int i:g[x]){if(i==fx){continue;}dfs(i,x);}
}
struct ST{pair<int,int>st[N+1][__lg(N+1)+1];void build(int n,int father[]){for(int i=1;i<=n;i++){st[i][0]={depth[rnk[i]],rnk[i]};}for(int i=1;(1<<i)<=n;i++){for(int x=1;x+(1<<i)-1<=n;x++){st[x][i]=min(st[x][i-1],st[x+(1<<i-1)][i-1]);}}}pair<int,int>query(int l,int r){int s=__lg(r-l+1);return min(st[l][s],st[r-(1<<s)+1][s]);}
}st;
int lca(int u,int v){if(u==v){return u;}if(dfn[u]>dfn[v]){swap(u,v);}return father[st.query(dfn[u]+1,dfn[v]).second];
}
int dist(int u,int v){return depth[u]+depth[v]-2*depth[lca(u,v)];
}
void pre(){dfs(1,0);st.build(n,father);
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;B=sqrt(n);for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}pre();vis[1]=true;for(int i=1;i<=m;i++){if(i%B==1){build();}int op,x;cin>>op>>x;switch(op){case 1:node.push_back(x);break;case 2:int ans=dis[x];for(int i:node){ans=min(ans,dist(x,i));}cout<<ans<<'\n';break;}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}