MYF

POJ 1470 Closest Common Ancestors

Posted on | In | | Visitors

题目链接

POJ 1470

方法：LCA最近公共祖先算法

题目分析

题目大意

题意看着真恶心，看了半天没看懂答案是怎么出来的。

n个点，然后跟着n行，每一行第一个数字表示树上的一个点，括号里的数字表示出度，跟着的表示连接的点的下标。然后给出m行，每行表示查询的两个点，找出两者的lca，统计出每个点作为lca的次数。

解析

模版题，n很小，统计一下即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#pragma comment(linker, "/STACK:10240000000,10240000000")///扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
using namespace std;
typedef long long LL;
const int N = 40005;

int n , m , pre[N] ,rt[N], mcnt;
int dis[N];
bool vis[N];
struct edge
{
    int x , next;
} e[N << 1];

int dep[N] , f[17][N] , Lev , s[N];///1<<16 < N, f[j][i] 表示i的第2^j个祖先

void dfs(int x , int fa)///也可以用bfs，但bfs不能统计节点孩子个数
{
    dep[x] = dep[fa] + 1;
    f[0][x] = fa , s[x] = 1;
    for (int i = pre[x] ; ~i ; i = e[i].next)
    {
        int y = e[i].x;
        if (y != fa)
        {
            dfs(y , x);
            s[x] += s[y];///节点x的孩子个数
        }
    }
}
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
    queue<int> q;
    q.push(rt);
    f[0][rt] = 0,dep[rt] = 1,vis[rt] = 1;
    while(!q.empty())
    {
        int fa = q.front();
        q.pop();
        for (int i = pre[fa] ; ~i ; i = e[i].next)
        {
            int x = e[i].x;
            if (!vis[x])
            {
                dep[x] = dep[fa] + 1;
                f[0][x] = fa ,vis[x] = 1;
                q.push(x);
            }
        }
    }
}
int LCA(int x , int y)
{
    if (dep[x] > dep[y]) swap(x , y);
    for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
        if (dep[y] - dep[x] >> i & 1)
            y = f[i][y];
    if (x == y) return y;
    for (int i = Lev ; i >= 0 ; -- i)
        if (f[i][x] != f[i][y])
            x = f[i][x] , y = f[i][y];
    return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
    for (int i = 0 ; i <= Lev ; ++ i)
        if (k >> i & 1)
            x = f[i][x];
    return x;
}
void init()
{
    memset(pre , -1 , sizeof(pre));
    memset(rt,0,sizeof(rt));
    memset(dis, 0, sizeof(dis));
    mcnt = 0;
}
void addedge(int x,int y)
{
    e[mcnt].x = y,
    e[mcnt].next = pre[x],
    pre[x] = mcnt ++;
}

int main()
{
    int i , j , x , y , z,anc,m,u,v;
    char ch2[2],ch1[2];
    while (scanf("%d",&n)!=EOF) {
        init();
        for (int i=0; i<n; i++) {
            scanf("%d:(%d)",&u,&m);
            for (int i=0; i<m; i++) {
                scanf("%d",&v);
                addedge(u,v);
                addedge(v,u);
                rt[v]  =u;
            }
        }

        for(int i=1; i<=n; i++)
        {
            if(rt[i]==0)
            {
                anc = i;
                break;
            }
        }
        dfs(anc , 0);
        for (j = 1 ; 1 << j < n ; ++ j)
            for (i = 1 ; i <= n ; ++ i)
                f[j][i] = f[j - 1][f[j - 1][i]];
        Lev = j - 1;
        int k;
        scanf("%d",&k);
        for (int i=0; i<k; i++) {
            scanf("%1s%d %d%1s",ch1,&x,&y,ch2);
            if (dep[x] < dep[y])
                swap(x , y);
            dis[LCA(x, y)]++;
        }
        
        for (int i=1; i<=n; i++) {
            if (dis[i]) {
                printf("%d:%d\n",i,dis[i]);
            }
        }
    }
    return 0;
}