[ZJ][LCA][online] d767. 血緣關係＠Morris' Blog

2012-10-05 16:28:05| 人氣1,702| 回應0 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

給一張祖譜,詢問 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≦N²)

輸出說明：

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

範例輸入： help

範例輸出：

提示：

背景知識： 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 nd, dp;
} ELE;
vector<int> g[maxN];
int lidx[maxN], tidx, M;
ELE tree[maxN<<2], stk[maxN<<1];
void dfs(int nd, int dep) {
    if(!lidx[nd])
        lidx[nd] = tidx;
    stk[tidx].nd = nd, stk[tidx++].dp = dep;
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        dfs(*it, dep+1);
        stk[tidx].nd = nd, stk[tidx++].dp = dep;
    }
}
void setTree(int n) {
    for(M = 1; M < n+1; M <<= 1);
    for(int i = 2*M-1; i > 0; i--) {
        if(i >= M)
            tree[i] = stk[i-M];
        else {
            if(tree[i<<1].dp < tree[i<<1|1].dp)
                tree[i] = tree[i<<1];
            else
                tree[i] = tree[i<<1|1];
        }
    }
}
ELE query(int s, int t) {
    static int i;
    ELE ans;
    ans.dp = 0xfffff;
    for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
        if(~s&1) {
            if(ans.dp > tree[s^1].dp)
                ans = tree[s^1];
        }
        if(t&1) {
            if(ans.dp > tree[t^1].dp)
                ans = tree[t^1];
        }
        s >>= 1, t >>= 1;
    }
    return ans;
}
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, i, j;
    while(scanf("%d %d", &n, &q) == 2) {
        for(i = 1; i <= n; i++) {
            g[i].clear();
            lidx[i] = 0;
            while(ReadInt(&x), x)
                g[i].push_back(x);
        }
        tidx = 0;
        dfs(1, 0);
        setTree(tidx);
        ELE ans;
        while(q--) {
            ReadInt(&i), ReadInt(&j);
            i = lidx[i], j = lidx[j];
            if(i > j)
                x = i, i = j, j = x;
            ans = query(i, j);
            printf("%d %d\n", ans.nd, -2*stk[lidx[ans.nd]].dp+stk[i].dp+stk[j].dp);
        }
    }
    return 0;
}

我要檢舉

#d767#血緣關係#LCA

台長： Morris

您可能對以下文章有興趣

[ZJ][dp] b123 最大矩形 (Area)

a171. 打印樹

a191. 在世界遙遠的彼方

[ZJ][字串處理] d477. 古韵之同心锁

人氣(1,702) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][LCA][offline] d767. 血緣關係
此分類上一篇:[ZJ][逆元、降階、高斯、短碼] a542. 行列式det(A)

回應(0)