342-E 题目大意
给定一颗\(n\)个节点的树，其中\(1\)号节点为红色，其余节点为蓝色
有m次操作，操作分为两种：
\(1.\)把节点\(x\)变为红色
\(2.\)询问节点\(x\)到最近红色节点的距离
Solution
对于操作\(2\)首先考虑两种暴力操作
\(1.\)对每次询问的\(x\)暴力\(BFS\)找到最近的红色节点，复杂度\(O(qn)\)
\(2.\)枚举之前所有标记为红色的节点，用求\(lca\)的方法来求出节点\(x\)到各个红色节点之间的距离，取最小值即可，复杂度\(O(q^2logn)\)
单独使用两个算法中的任意一个，复杂度都不过关，于是考虑结合二者算法的优点进行优化。
考虑对询问进行分块。
枚举询问块，用一个数组\(dis\)来记录在这个块之前，树中各个节点到最近的红色节点的距离。
对于块内的操作：
\(1.\)关于操作一我们用一个队列\(p\)来记录块内变为红色的节点
\(2.\)关于操作二我们枚举\(p\)中的所有元素对\(x\)求\(lca\)，和之前的\(dis[x]\)取最小值即为询问的答案
枚举完一个块之后，对队列\(p\)中的元素跑一遍多源\(BFS\)来更新\(dis\)数组，并清空队列\(p\)
时间复杂度\(O(n·\frac{q}{B}+B^2logn·\frac{q}{B}))\)，这里\(B\)是块长(这里\(B\)取\(\sqrt{\frac{n}{logn}}\)时最优)，注意到题目时限为\(5s\)，块长合理足够通过。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n,m;
cin>>n>>m;
vector<vector<int>> e(n+1);
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
vector<int> dis(n+1,1e9);
vector<int> dep(n+1),sz(n+1),son(n+1),top(n+1),fa(n+1);
function<void(int,int,int)> dfs1=[&](int x,int father,int d){
dis[x]=dep[x]=d,sz[x]=1,fa[x]=father;
for(auto y:e[x]){
if(y==father) continue;
dfs1(y,x,d+1);
sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
};
dfs1(1,0,0);
function<void(int,int)> dfs2=[&](int x,int t){
top[x]=t;
if(!son[x]) return;
dfs2(son[x],t);
for(auto y:e[x]){
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
};
dfs2(1,1);
function<int(int,int)> lca=[&](int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
};
vector<int> p;
function<void()> bfs=[&](){
queue<int> q;
for(auto c:p) q.push(c),dis[c]=0;
while(!q.empty()){
auto x=q.front();
q.pop();
for(auto y:e[x]){
if(dis[y]>dis[x]+1){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
};
int B=sqrt(m);
for(int i=1;i<=m;i++){
int op,x;
cin>>op>>x;
if(op&1){
p.push_back(x);
}else{
int res=dis[x];
for(auto y:p){
int z=lca(x,y);
res=min(res,dep[x]+dep[y]-2*dep[z]);
}
cout<<res<<" ";
}
if(i%B==0){
bfs();
p.clear();
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}