https://www.luogu.com.cn/problem/P8025
一道卡倍增不卡树剖的题,让我深刻理解了倍增常数较大,以及树剖优越性。
倍增T了一个点
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10;
int n,m,k,idx;
int e[M],ne[M],h[N],res[N];
int depth[N],fa[N][20];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){
memset(depth,0x3f,sizeof depth);
depth[1]=1,depth[0]=0;
queue<int>q;
q.push(1);
while(q.size()){
int t=q.front();
q.pop();
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(depth[j]>depth[t]+1){
depth[j]=depth[t]+1;
q.push(j);
fa[j][0]=t;
for(int k=1;k<=19;k++){
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b])swap(a,b);
for(int k=19;k>=0;k--){
if(depth[fa[a][k]]>=depth[b]){
a=fa[a][k];
}
}
if(a==b)return a;
for(int k=19;k>=0;k--){
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
bfs();
for(int i=0;i<k;i++){
int d,t;
scanf("%d%d",&d,&t);
int anc=lca(m,d);
int dis=depth[m]+depth[d]-2*depth[anc];
if(dis<=t)m=d;
else{
int dist=depth[m]-depth[anc];
if(t<=dist)
for(int k=19;k>=0;k--){
if(t>>k&1)m=fa[m][k];
}
else{
m=d,dist=dis-t;
for(int k=19;k>=0;k--){
if(dist>>k&1)m=fa[m][k];
}
}
}
printf("%d ",m);
}
return 0;
}
树剖AC
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10;
int n,m,k,idx,cnt;
int e[M],ne[M],h[N];
int siz[N],son[N],fa[N];
int dep[N],top[N],mp[N],id[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int father,int depth){
siz[u]=1,fa[u]=father,dep[u]=depth;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father)continue;
dfs1(j,u,depth+1);
siz[u]+=siz[j];
if(siz[son[u]]<siz[j])son[u]=j;
}
}
void dfs2(int u,int t){
id[u]=++cnt,mp[cnt]=u,top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==son[u]||j==fa[u])continue;
dfs2(j,j);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
return v;
}
int move(int u,int depth){
depth=dep[u]-depth;
while(dep[top[u]]>depth){
u=fa[top[u]];
}
return mp[id[u]-(dep[u]-depth)];
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dfs1(1,-1,1),dfs2(1,1);
while(k--){
int d,t;
scanf("%d%d",&d,&t);
int anc=lca(m,d);
int dis=dep[m]+dep[d]-2*dep[anc];
if(dis<=t)m=d;//m能到d
else{
if(dep[m]-dep[anc]>=t)m=move(m,t);//在m到LCA上
else m=move(d,dis-t);//在d到LCA上
}
printf("%d ",m);
}
return 0;
}