题意：给定一个n个点的数，初始只有1号点是红色，其余点都是蓝色，现在我们执行m次操作，操作分两种，一种是把某个蓝色点染成红色，一种是询问距离某个点最近的红点到询问点的距离。
N,M<=1e5
这道题有树链剖分的做法（目前还不会），不过题解给的是被叫做sqrt-optimization的方法，个人觉得很新奇。
下面先给出做法，然后给出我认为可以使用sqrt-optimization的条件。
我们对操作分块，假设分成T块。
首先，注意到一个事实，如果没有修改操作，全是查询操作，那么我们可以用一个多起点BFS在O(N)的时间复杂度内算出我们需要的答案，这样每次查询我们都可以用O(1)的复杂度解决了。
但是我们肯定不能每修改一下我们就做一遍多起点BFS，我们需要控制这个次数。
还有我们注意到一个事实，当我们考虑一个之前的修改对之后的查询的影响时，假设原先修改了一个点u，之后查询点v的答案时，我们可以借助LCA在O(logN)的时间更新答案（不会O(1)求LCA）
那么我们对操作分块，每一块执行完之后，我们去做一次多起点BFS。得到的就是当前每个点最新的答案了，然后我们处理下一块的操作时，我们去暴力处理每次修改对每次之后的查询的更新，假设这一块里面有x次修改，y次查询，那么显然有x+y=M/T，而时间复杂度最大是O(xylogN)的，根据均值不等式xy<=(x+y)^2/4，也是说O(xy)=O((M/T)^2*logN)，即每次在块内处理的复杂度是O((M/T)^2*logN)的。
而每块结束做多起点BFS的复杂度是O(T*N)的
那么整体的复杂度就是O(T*N+(M/T)^2*logN)的，再根据均值不等式，由于题目中N和M可以认为是同阶的，所以T取最小值当且仅当T*N=N^2/T^2*logN，也就是T^3=N*logN，T=(N*logN)^(1/3)时取最小值，此时整体复杂度是O(N^(4/3)*logN)的。
此题给了5秒，实测是可以过的。一般时间在2秒到2.5秒左右。
题解中给的分块是按照sqrt(M)分的，这里推导的结果是按M^(1/3)左右分块更优，实际跑的结果按sqrt(M)要略快一些，可能估算的时候忽略了一些常数，但实际会有影响吧，笔者做了一些测试，大约在块大小sz取M^(1/3)*log(M)*3.5的时候，时间复杂度相对最小。
接下来，我们来分析一下这道题采用这种分块处理询问的方法的适用条件。
首先，这里的修改和查询都是单点的。并且单点修改对在它之后发生的单点查询的更新的复杂度是不大的（我们认为O(1)或者O(logN)是不大的，可以接受的）。
并且，当问题静态化（没有修改）之后，我们可以在一个合理的复杂度(O(N)或者O(NlogN)内)通过维护一些信息高效地处理查询（O(1)或者O(logN)完成）。
此时我们就可以采用这种sqrt-optimization的方法，对操作分块，每完成一块就进行一次全部的处理，用来维护当前最新的信息，之后块内修改暴力处理对块内查询的更新（结合之前处理完的信息）。这样我们就在一个O(M*sqrt(N))或者O(M*sqrt(N)*logN)的时间复杂度内完成了整个问题。
我觉得运用这类思想解决整个问题的关键之一在于意识到用一个多起点BFS就可以高效地处理询问了，但是因为问题的动态性（带有修改），我们不能每次修改完都重新BFS一遍重新更新，所以我们需要控制重新BFS一遍的次数。
我们注意到，实际上，一次修改对后面询问的影响是有限的（受全部操作个数M的上限约束）。所以并不是任何时刻，我们都要处理出当前全部点的答案的，我们只需要处理出需要询问的点的答案即可。对于一个点的答案询问，我们去考虑这个询问前发生的所有修改对它的贡献，借助分块“大块维护，小块暴力”的基本思想，我们在时间序上分块，整块整块地维护完整正确的信息，小范围的块内就暴力更新一下。
或者这么说，BFS适合处理少修改，多询问的情况，而考虑每次修改对每次查询的暴力适合处理少修改，少询问的情况，因此我们对操作分块的目的就是控制BFS的次数，块内暴力，逐块处理询问。
最后附上代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
vector<int> red;
int head[maxn+5],father[maxn+5][20],dep[maxn+5],dep1[maxn+5];
int mn;
int lg[maxn+5];
int n,m,x,y;
int op[maxn+5],v[maxn+5];
int L[5000],R[5000];
bool vis[maxn+5];
int dis[maxn+5];
int ans[maxn+5];
queue<int> q;
inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
struct edge
{
int to,_next;
}G[2*maxn+5];
int num=0;
void add(int u,int v)
{
G[++num].to=v;
G[num]._next=head[u];
head[u]=num;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
father[u][0]=fa;
for (int i=1;(1<<i)<=dep[u];i++)
father[u][i]=father[father[u][i-1]][i-1];
for (int i=head[u];i;i=G[i]._next) {
int v=G[i].to;
if (v==fa) continue;
dfs(v,u);
}
}
int LCA(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
while (dep[x]>dep[y]) x=father[x][lg[dep[x]-dep[y]]];
if (x==y) return x;
for (int k=lg[dep[x]];k>=0;k--)
if (father[x][k]!=father[y][k]) {
x=father[x][k]; y=father[y][k];
}
return father[x][0];
}
int dist(int x,int y)
{
int t=LCA(x,y);
return dep[x]+dep[y]-2*dep[t];
}
void setLg(int n)
{
lg[0]=-1;
for (int i=1;i<=n;i++)
if (i&(i-1)) lg[i]=lg[i-1];
else lg[i]=lg[i-1]+1;
}
void bfs()
{
memset(vis,false,sizeof(vis));
while (q.size()) q.pop();
for (int i=0;i<red.size();i++) {
q.push(red[i]); vis[red[i]]=true; dis[red[i]]=0;
}
while (q.size()) {
int u=q.front(); q.pop();
for (int i=head[u];i;i=G[i]._next) {
int v=G[i].to;
if (!vis[v]) {
q.push(v);
vis[v]=true;
dis[v]=dis[u]+1;
}
}
}
}
int main()
{
setLg(maxn);
//scanf("%d%d",&n,&q);
n=read(); m=read();
for (int i=0;i<n-1;i++) {
//scanf("%d%d",&x,&y);
x=read(); y=read();
add(x,y); add(y,x);
}
dfs(1,0);
int sz=pow(4.5*m*log(n)/log(2.0),1.0/3)+1;
int k=m/sz;
for (int i=1;i<=m;i++) op[i]=read(),v[i]=read();
for (int i=1;i<=k;i++) L[i]=(i-1)*sz+1,R[i]=i*sz;
if (k*sz<m) {
L[k+1]=k*sz+1; R[k+1]=m; k++;
}
red.push_back(1);
memset(dis,0x3f,sizeof(dis));
for (int i=1;i<=k;i++) {
//printf("debug %d
",i);
bfs();
for (int l=L[i];l<=R[i];l++)
if (op[l]==2) ans[l]=dis[v[l]];
for (int l=L[i];l<=R[i];l++)
if (op[l]==1)
for (int r=l+1;r<=R[i];r++)
if (op[r]==2) ans[r]=min(ans[r],dist(v[r],v[l]));
for (int l=L[i];l<=R[i];l++)
if (op[l]==1) red.push_back(v[l]);
//printf("before bfs
");
}
for (int i=1;i<=m;i++)
if (op[i]==2) printf("%d
",ans[i]);
return 0;
}