poj 1470 Closest Common Ancestors 【Tarjan 离线 LCA】

女爷i 2022-08-13 16:40 156阅读 0赞

题目：[poj 1470 Closest Common Ancestors][]

题意：给出一个树，一些询问。求LCA的个数、

分析：很简单的模板题目，但是模板不够优秀，一直wa...RE，各种错误一下午，终于发现自己模板的漏洞了。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    #define N 1010
    #define M 20010
    
    struct Node
    {
        int to,val;
    };
    vector<Node> g[N];
    struct ask{
        int u,v,lca;
    };
    vector<ask> e;
    vector<int> query[N];
    int fa[N],ance[N],dir[N];
    bool vis[N];
    
    inline void add_Node(int u ,int v,int w)
    {
        g[u].push_back((Node){v,w});
        g[v].push_back((Node){u,w});
    }
    
    inline void add_ask(int u ,int v )
    {
        e.push_back((ask){u,v,-1});
        e.push_back((ask){v,u,-1});
        int len = e.size()-1;
        query[v].push_back(len);
        query[u].push_back(len-1);
    }
    
    int find(int x){
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    
    void Tarjan(int u,int val)
    {
        vis[u] = true;
        ance[u] = fa[u] = u;
        dir[u] = val;
        for(int i=0;i<g[u].size();i++)
        {
            Node tmp = g[u][i];
            if(!vis[tmp.to])
            {
                Tarjan(tmp.to,val+tmp.val);
                fa[tmp.to] = u;
            }
        }
        for(int i=0;i<query[u].size();i++)
        {
            int num = query[u][i];
            ask& tmp = e[num];
            if(vis[tmp.v])
            {
                tmp.lca = e[num^1].lca = ance[find(tmp.v)];
            }
        }
    }
    int ans[N],flag[N];
    void Clear(int n)
    {
        memset(vis,false,sizeof(vis));
        memset(ans,0,sizeof(ans));
        memset(flag,0,sizeof(flag));
        for(int i=0;i<=n;i++){
            g[i].clear();
            query[i].clear();
        }
        e.clear();
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n;
        int u,x,m;
        char ch;
        while(scanf("%d",&n)!=EOF)
        {
            Clear(n);
            for(int i=1;i<=n;i++)
            {
                scanf("%d:(%d)",&u,&m);
                while(m--)
                {
                    scanf("%d",&x);
                    flag[x]=true;
                    add_Node(x,u,1);
                }
            }
            int Q;
            scanf("%d",&Q);
            for(int i=1;i<=Q;i++)
            {
                cin>>ch;
                scanf("%d%d",&u,&x);
                cin>>ch;
                add_ask(u,x);
            }
            int root;
            for(int i=1;i<=n;i++)
              if(!flag[i])
              {
                  root=i;
                  break;
              }
            Tarjan(root,0);
            for(int i = 0;i< Q;i++)
            {
                ans[e[i*2].lca]++;
            }
            for(int i = 1; i<= N;i++)
            {
                if(ans[i])
                    printf("%d:%d\n",i,ans[i]);
            }
        }
        return 0;
    }

[poj 1470 Closest Common Ancestors]: http://poj.org/problem?id=1470