POJ 1470 Closest Common Ancestors(LCA&RMQ)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意比较费劲：输入看起来很麻烦。处理括号冒号的时候是用%1s就可以。还有就是注意它有根节点。。。Q次查询

在线st算法

/*************************************************************************

    > File Name:            3.cpp

    > Author:               Howe_Young

    > Mail:                 1013410795@qq.com

    > Created Time:         2015年10月08日 星期四 19时03分30秒

 ************************************************************************/

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = ;

struct Edge {

    int to, next;

}edge[maxn<<];

int tot, head[maxn];

int ans[maxn];

int Euler[maxn<<];

int R[maxn];

int dep[maxn];

int dp[maxn<<][]; // RMQ

bool in[maxn];

int cnt;

void init()

{

    cnt = ;

    tot = ;

    memset(head, -, sizeof(head));

    memset(ans, , sizeof(ans));

    memset(in, false, sizeof(in));

}

void addedge(int u, int v)

{

    edge[tot].to = v;

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

    head[u] = tot++;

}

void dfs(int u, int depth)

{

    Euler[++cnt] = u;

    R[u] = cnt;

    dep[cnt] = depth;

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

    {

        int v = edge[i].to;

        dfs(v, depth + );

        Euler[++cnt] = u;

        dep[cnt] = depth;

    }

}

void RMQ(int n)

{

    for (int i = ; i <= n; i++) dp[i][] = i;

    int m = (int)(log(n) / log());

    for (int j = ; j <= m; j++)

    {

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

            dp[i][j] = dep[dp[i][j - ]] < dep[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];

    }

}

int query(int u, int v)

{

    int l = R[u], r = R[v];

    if (l > r) swap(l, r);

    int k = (int)(log(r - l + ) / log());

    int lca = dep[dp[l][k]] < dep[dp[r - ( << k) + ][k]] ? dp[l][k] : dp[r - ( << k) + ][k];

    return Euler[lca];

}

int main()

{

    int n;

    while (~scanf("%d", &n))

    {

        init();

        char s1[], s2[];

        int u, v, m;

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

        {

            scanf("%d %1s %1s %d %1s", &u, s1, s1, &m, s2);

            for (int j = ; j < m; j++)

            {

                scanf("%d", &v);

                addedge(u, v);

                in[v] = true;

            }

        }

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

            if (!in[i])

            {

                dfs(i, );

                break;

            }

        RMQ(cnt);

        int Q;

        scanf("%d", &Q);

        while (Q--)

        {

            scanf("%1s %d %d %1s", s1, &u, &v, s2);

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

        }

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

            if (ans[i])

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

    }

    return ;

}

离线tarjan算法：

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = ;//节点

const int maxm = ;//最大查询数

struct Edge {

    int to, next;

}edge[maxn * ];

int tot, head[maxn];

struct Query {

    int q, next;

    int index;

}query[maxm * ];

int cnt, h[maxn];

int fa[maxn];

int r[maxn];

int ancestor[maxn];

int ans[maxm];

int Q;

bool vis[maxn];

void init(int n)

{

    Q = ;

    tot  = ;

    cnt = ;

    memset(head, -, sizeof(head));

    memset(h, -, sizeof(h));

    memset(fa, -, sizeof(fa));

    memset(ancestor, , sizeof(ancestor));

    memset(vis, false, sizeof(vis));

    for (int i = ; i <= n; i++) r[i] = ;

}

void addedge(int u, int v)

{

    edge[tot].to = v;

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

    head[u] = tot++;

}

void addquery(int u, int v, int index)

{

    query[cnt].q = v;

    query[cnt].index = index;

    query[cnt].next = h[u];

    h[u] = cnt++;

}

int find(int x)

{

    if (fa[x] == -) return x;

    return fa[x] = find(fa[x]);

}

void Union(int x, int y)

{

    int tx = find(x);

    int ty = find(y);

    if (tx != ty)

    {

        if (tx < ty)

        {

            fa[tx] = ty;

            r[ty] += r[tx];

        }

        else

        {

            fa[ty] = tx;

            r[tx] += r[ty];

        }

    }

}

void LCA(int u)

{

    vis[u] = true;

    ancestor[u] = u;

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

    {

        int v = edge[i].to;

        if (vis[v]) continue;

        LCA(v);

        Union(u, v);

        ancestor[find(u)] = u;

    }

    for (int i = h[u]; i != -; i = query[i].next)

    {

        int v = query[i].q;

        if (vis[v])

        {

            ans[query[i].index] = ancestor[find(v)];

        }

    }

}

int res[maxn];

bool in[maxn];

int main()

{

    int n;

    while (~scanf("%d", &n))

    {

        init(n);

        memset(in, false, sizeof(in));

        int u, v, m;

        char ch[];

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

        {

            scanf("%d %1s %1s %d %1s", &u, ch, ch, &m, ch);

            for (int j = ; j < m; j++)

            {

                scanf("%d", &v);

                in[v] = true;

                addedge(u, v);

                addedge(v, u);

            }

        }

        int q;

        scanf("%d", &q);

        while (q--)

        {

            scanf("%1s %d %d %1s", ch, &u, &v, ch);

            addquery(u, v, Q);

            addquery(v, u, Q++);

        }

        int root;

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

        {

            if (!in[i])

            {

                root = i;

                break;

            }

        }

        LCA(root);

        memset(res, , sizeof(res));

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

            res[ans[i]]++;

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

            if (res[i])

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

    }

    return ;

}