本文主要是介绍(CodeForces) E. Xenia and Tree (lca+分块+最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
题意：给定一棵树，一开始只有1为红，其他点为蓝。两种操作：1，把一个点染成红点。2，询问一个点到最近红点的距离。
解：数据量只有1e5,n根号n*log应该是可以的，主要是这个染色后，我们不能每一次染色后都去跑一次最短路（bfs就可以了），所以我们当修改数目达到根号n时再去进行一次最短路，查询是如果有点是未更新状态，我们可以通过lca来求得两点的距离，这样就可以保证复杂度是可行的。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e5+5;
const int maxbit=20;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m,base;
int dep[N],fa[N][maxbit],lg[N],dis[N];//dis:到红点最近的距离
vector<int> G[N];
bool vis[N];
il void init(){lg[0]=-1,base=sqrt(n)+1,vis[1]=1;for(int i=1;i<N;++i) lg[i]=lg[i>>1]+1;
}
il void dfs(int np,int f){dep[np]=dep[f]+1,fa[np][0]=f,dis[np]=dep[np]-1;for(int i=1;i<=lg[dep[np]]+1;++i) fa[np][i]=fa[fa[np][i-1]][i-1];for(auto to:G[np]){if(to!=f) dfs(to,np);}
}
il int lca(int u,int v){if(dep[u]<dep[v]) swap(u,v);while(dep[u]!=dep[v]) u=fa[u][lg[dep[u]-dep[v]]];if(u==v) return u;for(int i=lg[dep[u]];i>=0;--i){if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];}return fa[u][0];
}
il int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int q[N],cnt=0;
queue<int> qe;
il void solve(){int x;while(!qe.empty()){x=qe.front(),qe.pop();for(auto to:G[x]){if(dis[to]>dis[x]+1){dis[to]=dis[x]+1;qe.push(to);}}}
}
il void update(int x){if(vis[x]) return;vis[x]=1,dis[x]=0,q[++cnt]=x,qe.push(x);if(cnt==base){solve();cnt=0;}
}
il int query(int x){int ans=dis[x];for(int i=1;i<=cnt;++i) ans=min(ans,dist(q[i],x));return ans;
}
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;init();for(int i=1,x,y;i<=n-1;++i){cin>>x>>y;G[x].pb(y),G[y].pb(x);}dfs(1,0);for(int i=1,op,x;i<=m;++i){cin>>op>>x;if(op==1) update(x);else cout<<query(x)<<endl;}return 0;
}
这篇关于(CodeForces) E. Xenia and Tree (lca+分块+最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
