2012-09-22 16:29:42Morris
[ZJ][樹形dp] a265. 紅黑樹
內容 ：
紅黑樹是一種自我平衡二分搜尋樹(self-balance binary search tree)，是一種資料結構。它是複雜的，但它的操作有着良好的最壞情況運行時間，並且在實踐中是高效的:它可以在O(log n)時間內做查找，插入和刪除，這裡的n是樹中元素的數目。
紅黑樹是每個節點都帶有顏色屬性的二分搜尋樹，顏色為紅色或黑色。除了一般二分搜尋樹的要求外(左子點<父節點<右子點)，對於任何有效的紅黑樹增加了如下的額外要求：
性質1. 節點是紅色或黑色。
性質2. 根(root)是黑色。
性質3. 所有葉子(leaves)都是黑色（葉子是NIL節點）。
性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
對於紅黑樹的操作(查找、插入、刪除、旋轉)是有點複雜的。本題給你一個較簡單的工作：判斷一棵尚未上色的樹能不能經由某種上色而成為一棵紅黑樹(Red-Black Tree)，如果可以，又有多少種上色方式可以使它成為紅黑樹?
輸入說明
：
每組測資的第一行輸入為正整數n，代表共有幾個節點。接下來的n-1行，每行有兩個整數P、S，代表S是P的子節點。其中1<=n<=31，-100<=S、P<=100。測資保證輸入的一定是棵二元樹，並且任意兩點都不相同。注意性質3.中所有的NIL葉子都不會被輸入也不會被計算在n值裡，範例測資的第一筆即為上圖。以EOF判斷輸入結束。
輸出說明
：
請先輸出這是第幾筆測資，格式請參考範例輸出。然後輸出一個整數代表該筆測資的樹有多少種上色方式能使它成為一棵紅黑樹，如果它不能是棵紅黑樹的話則輸出0。
範例輸入
：
10 1 6 8 11 8 1 17 15 13 17 13 8 17 25 25 22 25 27 1 5 1 0 1 5 5 -1 5 6
範例輸出 ：
Case 1:3 Case 2:1 Case 3:0
提示
：
出處
：
2011成功高中校內賽複賽 第一題
(管理：david942j)
又要檢查錯誤二元樹, 真是夠惱人的
#include <stdio.h>
#include <string.h>
#define NIL -0xffff
typedef struct {
int v, L, R;
int r[40], b[40];
} Nd;
Nd D[80];
int err;
void dfs(int nd, int l, int r) {
if(D[nd].v != NIL && (D[nd].v < l || D[nd].v > r))
err = 1;
if(err) return;
if(D[nd].L) dfs(D[nd].L, l, D[nd].v);
if(D[nd].R) dfs(D[nd].R, D[nd].v, r);
if(!D[nd].L && !D[nd].R) { /*leaf*/
D[nd].b[1] = 1;
} else {
int i, blw, brw, rlw, rrw;
for(i = 0; i < 39; i++) {
if(D[nd].L) {
blw = D[D[nd].L].b[i];
rlw = D[D[nd].L].r[i];
}
if(D[nd].R) {
brw = D[D[nd].R].b[i];
rrw = D[D[nd].R].r[i];
}
if(!D[nd].L) D[nd].r[i] = brw;
else if(!D[nd].R) D[nd].r[i] = blw;
else D[nd].r[i] = blw*brw;
if(!D[nd].L) D[nd].b[i+1] = brw+rrw;
else if(!D[nd].R) D[nd].b[i+1] = blw+rlw;
else D[nd].b[i+1] = (blw+rlw)*(brw+rrw);
}
}
}
int main() {
int n, p, s, x, y;
int i, j, cases = 0;
while(scanf("%d", &n) == 1) {
memset(D, 0, sizeof(D));
int size = 1, in[40] = {};
err = 0;
for(i = 1; i < n; i++) {
scanf("%d %d", &p, &s);
for(j = 1; j < size; j++)
if(D[j].v == p)
break;
x = j;
if(x == size) {D[x].v = p, size++;}
for(j = 1; j < size; j++)
if(D[j].v == s)
break;
y = j;
if(y == size) {D[y].v = s, size++;}
if(p > s) {
if(D[x].L) err = 1;
D[x].L = y;
} else {
if(D[x].R) err = 1;
D[x].R = y;
}
in[y] = 1;
}
if(size != n+1) err = 1;
int rt = 0;
for(i = 1; i < size; i++) {
if(!in[i]) {
if(rt) err = 1;
rt = i;
}
}
int os = size;
for(i = 1; i < os; i++) {
if(!D[i].L) {
D[i].L = size;
D[size].v = NIL;
size++;
}
if(!D[i].R) {
D[i].R = size;
D[size].v = NIL;
size++;
}
}
dfs(rt, -0xffff, 0xffff);
printf("Case %d:", ++cases);
if(n == 1) {puts("1");continue;}
if(err) {
puts("0");
continue;
}
int ans = 0;
for(i = 0; i < 40; i++)
ans += D[rt].b[i];
printf("%d\n", ans);
}
return 0;
}
又要檢查錯誤二元樹, 真是夠惱人的
#include <stdio.h>
#include <string.h>
#define NIL -0xffff
typedef struct {
int v, L, R;
int r[40], b[40];
} Nd;
Nd D[80];
int err;
void dfs(int nd, int l, int r) {
if(D[nd].v != NIL && (D[nd].v < l || D[nd].v > r))
err = 1;
if(err) return;
if(D[nd].L) dfs(D[nd].L, l, D[nd].v);
if(D[nd].R) dfs(D[nd].R, D[nd].v, r);
if(!D[nd].L && !D[nd].R) { /*leaf*/
D[nd].b[1] = 1;
} else {
int i, blw, brw, rlw, rrw;
for(i = 0; i < 39; i++) {
if(D[nd].L) {
blw = D[D[nd].L].b[i];
rlw = D[D[nd].L].r[i];
}
if(D[nd].R) {
brw = D[D[nd].R].b[i];
rrw = D[D[nd].R].r[i];
}
if(!D[nd].L) D[nd].r[i] = brw;
else if(!D[nd].R) D[nd].r[i] = blw;
else D[nd].r[i] = blw*brw;
if(!D[nd].L) D[nd].b[i+1] = brw+rrw;
else if(!D[nd].R) D[nd].b[i+1] = blw+rlw;
else D[nd].b[i+1] = (blw+rlw)*(brw+rrw);
}
}
}
int main() {
int n, p, s, x, y;
int i, j, cases = 0;
while(scanf("%d", &n) == 1) {
memset(D, 0, sizeof(D));
int size = 1, in[40] = {};
err = 0;
for(i = 1; i < n; i++) {
scanf("%d %d", &p, &s);
for(j = 1; j < size; j++)
if(D[j].v == p)
break;
x = j;
if(x == size) {D[x].v = p, size++;}
for(j = 1; j < size; j++)
if(D[j].v == s)
break;
y = j;
if(y == size) {D[y].v = s, size++;}
if(p > s) {
if(D[x].L) err = 1;
D[x].L = y;
} else {
if(D[x].R) err = 1;
D[x].R = y;
}
in[y] = 1;
}
if(size != n+1) err = 1;
int rt = 0;
for(i = 1; i < size; i++) {
if(!in[i]) {
if(rt) err = 1;
rt = i;
}
}
int os = size;
for(i = 1; i < os; i++) {
if(!D[i].L) {
D[i].L = size;
D[size].v = NIL;
size++;
}
if(!D[i].R) {
D[i].R = size;
D[size].v = NIL;
size++;
}
}
dfs(rt, -0xffff, 0xffff);
printf("Case %d:", ++cases);
if(n == 1) {puts("1");continue;}
if(err) {
puts("0");
continue;
}
int ans = 0;
for(i = 0; i < 40; i++)
ans += D[rt].b[i];
printf("%d\n", ans);
}
return 0;
}