poj1470 LCA倍增法

倍增法模板题

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define maxn 1000

#define DEG 20

struct Edge{

    int to,next;

}edge[maxn*maxn*];

int head[maxn],tot;

void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

int fa[maxn][DEG];

int deg[maxn];

void bfs(int root){

    queue<int> que;

    deg[root]=;

    fa[root][]=root;

    que.push(root);

    while(!que.empty()){

        int tmp=que.front();

        que.pop();

        for(int i=;i<DEG;i++)

            fa[tmp][i]=fa[fa[tmp][i-]][i-];

        for(int i=head[tmp];i!=-;i=edge[i].next){

            int v=edge[i].to;

            if(v==fa[tmp][]) continue;

            deg[v]=deg[tmp]+;

            fa[v][]=tmp;

            que.push(v);

        }

    }

}

int lca(int u,int v){

    if(deg[u]>deg[v]) swap(u,v);

    int hu=deg[u],hv=deg[v],tu=u,tv=v;

    for(int det=hv-hu,i=;det;det>>=,i++)

        if(det&) tv=fa[tv][i];//将uv提到同一深度

    if(tu==tv) return tu;

    for(int i=DEG-;i>=;i--){

        if(fa[tu][i]==fa[tv][i]) continue;

        tu=fa[tu][i];

        tv=fa[tv][i];

    }

    return fa[tu][];

}

int ans[maxn],flag[maxn];

void init(){

    tot=;

    memset(ans,,sizeof ans);

    memset(head,-,sizeof head);

    memset(flag,,sizeof flag);

}

int main(){

    int n,u,v,m,q;

    while(scanf("%d",&n)==){

        init();

        for(int i=;i<=n;i++){

            scanf("%d:(%d)",&u,&m);

            while(m--){

                scanf("%d",&v);

                addedge(u,v);

                addedge(v,u);

                flag[v]=true;

            }

        }

        int root;

        for(int i=;i<=n;i++) if(!flag[i]){root=i;break;}

        bfs(root);

        scanf("%d",&q);

        char c;

        while(q--){

            cin>>c;

            scanf("%d %d)",&u,&v);

            ans[lca(u,v)]++;

        }

        for(int i=;i<=n;i++)

            if(ans[i]) printf("%d:%d\n",i,ans[i]);

    }

    return ;

}