2012-10-05 19:36:33Morris

[ZJ][LCA][offline] d767. 血緣關係

內容 :

給一張祖譜,詢問 A , B 兩人關係最近的共同祖先 以及 A , B 之間的親等
example 1

親等計算 : 往上算到與要計算的人共同祖先處,再往下算到那個人,數多少就是幾親等。

※ 輸入的人的編號,必為 1~N ,而兒女編號必大於父母本身的編號。

輸入說明 :

第一行兩個數字 N , Q
分別代表接下來會有 N 行數字分別代表該人的兒女編號(以 0 表結束),
再來會有 Q 行
每行上會有兩個數字 A , B ,代表要求出 A , B 兩人的關係最近的共同祖先
以及 A , B 之間的親等。
詳細請參考Sample Input
(N≦3,0000,    1≦A,B≦N,     Q≦N2)

輸出說明 :

輸出兩個數字最近的共同祖先 以及 A , B 之間的親等

範例輸入 :help

7 6
2 3 0
4 5 0
6 7 0
0
0
0
0
4 5
4 2
4 4
4 3
1 7
2 3

範例輸出 :

2 2
2 1
4 0
1 3
1 2
1 2

提示 :

背景知識: RMQ

※ 在此未符合實際事實,暫定一個人的兒女不超過6個

Ranged Minimum/Maximum Query(RMQ)
Least Common Ancestors (LCA)

出處 :

RMQ & LCA (管理:morris1028)

學習文章  <- 請點閱


#include <stdio.h>
#include <vector>
#define maxN 32768
using namespace std;
typedef struct {
    int q, i;
} Qi;
vector<int> g[maxN];
vector<Qi> qu[maxN];
int r[maxN], p[maxN], dp[maxN], used[maxN];
int oput[500000][2];
int findp(int x) {
    return p[x] == x ? x : p[x]=findp(p[x]);
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    p[x] = y;
}
void dfs(int nd, int dep) {
    dp[nd] = dep, used[nd] = 1;
    for(vector<Qi>::iterator it = qu[nd].begin();
        it != qu[nd].end(); it++) {
        if(used[it->q]) {
            oput[it->i][0] = findp(it->q);
            oput[it->i][1] = dp[nd]+dp[it->q]-2*dp[findp(it->q)];
        }
    }
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        dfs(*it, dep+1);
        joint(*it, nd);
    }
}
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, q, x, y, i, j;
    while(scanf("%d %d", &n, &q) == 2) {
        for(i = 1; i <= n; i++) {
            g[i].clear(), r[i] = 1, p[i] = i, used[i] = 0;
            while(ReadInt(&x), x)
                g[i].push_back(x);
        }
        Qi tmp;
        for(i = 0; i < q; i++) {
            ReadInt(&x), ReadInt(&y);
            tmp.i = i, tmp.q = y;
            qu[x].push_back(tmp);
            tmp.q = x;
            qu[y].push_back(tmp);
        }
        dfs(1, 0);
        for(i = 0; i < q; i++)
            printf("%d %d\n", oput[i][0], oput[i][1]);
    }
    return 0;
}