E. Xenia and Tree

题目链接

标签：

LCA，bfs，分块

题意：

给定一颗n个结点的树，先把1号节点染色，其他节点初始状态都是未染色，会给我们m个询问，每个询问有两种类型，“1 x”表示把x结点染色，“2 x”表示求到x点最近的染色的点的距离。

题解：

  1. 题目中的数据范围是1e5级别，对于询问2可以直接先预处理dis，然后直接进行查询，但是新染色的话需要重新更新所有dis，那么时间复杂度会达到n^2。
  2. 我们可以进行分块，每个块大小为sqrt(n)，如果新染色的点比较少，那么加入vector中，然后查询的时候，只要查询该点到已经更新的点的最小距离和未更新的染色的点的LCA来确定两个点的最小距离，两者取个较小值就是我们要的答案。
  3. 但vector中的点达到sqrt(n)，那么就把vector中的点拿出来进行更新。
  4. LCA是log级别的，块大小也是log级别，这样时间复杂度达到n*sqrt(m)。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;

int n,m,base;
int dep[N],fa[N][20],lg[N],dis[N];
vector<int> G[N];
bool vis[N];
inline 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;
}
inline 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);
	}
}
inline 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];
}
inline int dist(int u,int v){
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}

int q[N],cnt=0;
queue<int>st;
void updata(int u){
    vis[u]=1;
    q[++cnt]=u;
    st.push(u);
    dis[u]=0;
    if(cnt==base){
        while(!st.empty()){
            int v=st.front();
            st.pop();
            for(auto x:G[v]){
                if(dis[x]>dis[v]+1){
                    dis[x]=dis[v]+1;
                    st.push(x);
                }
            }
        }
        cnt=0;
    }
}

int query(int u){
    int ans=dis[u];
    for(int i=1;i<=cnt;i++)ans=min(ans,dist(q[i],u));
    return ans;
}

void solve(){
    cin>>n>>m;
    init();
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y),G[y].push_back(x);
    }
    dfs(1,0);
    while(m--){
        int x,y;
        cin>>x>>y;
        if(x==1)updata(y);
        else cout<<query(y)<<endl;
    }

}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}