2012-10-05 16:28:05Morris
[ZJ][LCA][online] d767. 血緣關係
內容 ：
給一張祖譜,詢問 A , B 兩人關係最近的共同祖先 以及 A , B 之間的親等
example 1
親等計算 : 往上算到與要計算的人共同祖先處，再往下算到那個人，數多少就是幾親等。
※ 輸入的人的編號，必為 1~N ，而兒女編號必大於父母本身的編號。
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 之間的親等
範例輸入
：
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 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;
}
#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;
}