倍增法求公共祖先

倍增发：

快速求祖先

代码

void dfs1(int u,int f)
{
    fa[u]=f;
    vis[u]=1;
    dep[u]=dep[f]+1;
    for(ri i=1;(1<<i)<=dep[u];i++)
     anc[u][i]=anc[anc[u][i-1]][i-1];
     for(ri i=head[u];i;i=bian[i].net)
     {
         int v=bian[i].to;
         if(vis[v]==1) continue ;
           anc[v][0]=u;
           dfs1(v,u);
     }
}

View Code

求公共祖先：

int LCA(int x,int y)
{
    if(dep[x]>dep[y]) swap(x,y);
    for(ri i=20;i>=0;i--)
    {
        if(dep[f[y][i]]>=dep[x])
        {
            y=f[y][i];
        }
        if(x==y) return x;
    }
    for(ri i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i],y=f[y][i];
        }
    }
    return f[x][0];
}

View Code

找祖先：一定要跟新

题目：

Panel 国将举办名为数字游戏的年度表演。每个省派出一名选手。

国家有 nn 个编号从 11 到 nn 的省，每个省刚好有一条路径将其与其他省相连。第 ii 个省出来的代表有 2^i2 
i
  名粉丝。

今年，主席打算削减开支，他想要踢掉 kk 个选手。但是，被踢掉的选手的省将很 angry 并且不会让别的任何人从这个省经过。

主席想确保所有剩下选手的省都互相可达，他也希望最大化参与表演的选手的粉丝数。

主席该踢掉哪些选手呢？

输入格式
输入 n,kn,k 。（ k < n leq 10^6k<n≤10 
6
  ）

下来是 n-1n−1 行，一行两个数，代表一条道路的起终点。

输出格式
升序输出要踢掉的选手编号。

View Code

代码：

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ri register int
const int M =2000005;
const int N =1000005;
int head[N];
struct setbian{
    int net,to;
}bian[M];
int cent;
void add(int a,int b)
{
    bian[++cent].net=head[a],head[a]=cent;
    bian[cent].to=b;
}
int anc[N][30];
int n,vis[N],fa[N],dep[N];
void dfs1(int u,int f)
{
    fa[u]=f;
    vis[u]=1;
    dep[u]=dep[f]+1;
    for(ri i=1;(1<<i)<=dep[u];i++)
     anc[u][i]=anc[anc[u][i-1]][i-1];
     for(ri i=head[u];i;i=bian[i].net)
     {
         int v=bian[i].to;
         if(vis[v]==1) continue ;
           anc[v][0]=u;
           dfs1(v,u);
     }
}
void dfs2(int u,int tp)
{
    vis[u]=1;
    if(u==tp) return;
    dfs2(fa[u],tp);
}
int path[N],m;
int main(){
    scanf("%d%d",&n,&m);
    m=n-m;
    memset(anc,-1,sizeof anc);
    for(ri i=1;i<n;i++)
    {
        int a,b;
        scanf("%ld%ld",&a,&b); 
        add(a,b);add(b,a);
    }
    dfs1(n,-1);
    memset(vis,0,sizeof vis);
    vis[n]=1;
    int help=1;
    for(ri i=n-1;i>=1;i--)
    {    
       int trmp=i;
        if(vis[i]==1) continue;
        for(ri j=20;j>=0;j--)
        {
            if(anc[i][j]==-1) continue;  
            if(vis[anc[trmp][j]]==0)   // 一定要跟新 
             {
               trmp=anc[trmp][j];break;
             }
        }
        if(dep[i]-dep[trmp]+help+1<=m)
        dfs2(i,trmp),help+=dep[i]-dep[trmp]+1;
        if(help==m) break;    
    }
    int trmp=0;
    for(ri i=1;i<=n;i++) 
    {
        if(vis[i]==0) path[++trmp]=i;
    }
    for(ri i=1;i<=trmp;i++)
    printf("%d ",path[i]);                                                   
}

View Code

https://i-beta.cnblogs.com/posts/edit;postId=11760661

倍增法 求公共祖先

倍增法求公共祖先