大神们好像都用的Tarjan 就我奇葩地用在线倍增……

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=1000+10,maxh=32;
int n,q,tot,ans[maxn];
int dep[maxn],anc[maxn][maxh];
int head[maxn],p[maxn*2],next[maxn*2];
bool vis[maxn];
void dfs(int root)
{
    static int stc[maxn],top;
    for(int i=0;i<maxh;i++) anc[root][i]=root;
    dep[root]=1;
    stc[++top]=root;
    while(top)
    {
        int x=stc[top];
        if(x!=root)
        {
            for(int i=1;i<maxh;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
        }
        for(int &i=head[x];i;i=next[i])
        {
            int y=p[i];
            if(y!=anc[x][0])
            {
                dep[y]=dep[x]+1;
                anc[y][0]=x;
                stc[++top]=y;
            }
        }
        while(top&&!head[stc[top]]) --top;
    }
}
void update(int &x,int h)
{
    for(int i=0;h;i++)
    {
        (h&1)&&(x=anc[x][i]);
        h>>=1;
    }
    return ;
}
int LCA(int s,int t)
{
    if(dep[s]>dep[t])   swap(s,t);
    update(t,dep[t]-dep[s]);
    if(s==t)    return s;
    for(int i;;)
    {
        for(i=0;anc[s][i]!=anc[t][i];i++);
        if(i==0)    return anc[s][0];
        s=anc[s][i-1];  t=anc[t][i-1];
    }
}
void clear()
{
    n=q=tot=0;
    memset(ans,0,sizeof ans);
    memset(anc,0,sizeof anc);  memset(dep,0,sizeof dep);
    memset(head,0,sizeof head);  memset(next,0,sizeof next);  memset(p,0,sizeof p);
    memset(vis,false,sizeof vis);
    return ;
}
void get_int(int&num)
{
    char c; bool f=false;
    for(;c=getchar(),c<'0'||c>'9';(c=='-')&&(f=true));
    for(num=c-48;c=getchar(),c>='0'&&c<='9';num=num*10+c-48);
    f&&(num=-num);
    return ;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1,u,cnt;i<=n;i++)
        {
            get_int(u);
            get_int(cnt);
            for(int j=1,v;j<=cnt;j++)
            {
                get_int(v);
                p[++tot]=v; next[tot]=head[u]; head[u]=tot;
                vis[v]=true;
            }
        }
        for(int i=1;i<=n;i++)
            if(!vis[i])
            {
                dfs(i);
                break;
            }
        get_int(q);
        for(int i=1,s,t;i<=q;i++)
        {
            get_int(s);
            get_int(t);
            ++ans[LCA(s,t)];
        }
        for(int i=1;i<=n;i++)   if(ans[i])  printf("%d:%d\n",i,ans[i]);
        clear();
    }
    return 0;
}

• Re:zojAC了 poj上怎么也过不了 求解 (12) 111_a 2019-12-19 17:35:57