目錄
1,題目描述
題目大意
2,思路
3,AC代碼
4,解題過程
1,題目描述
Sample Input:
6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.
題目大意
找出一棵樹中兩個節點的LCA(lowest common ancestor),注意節點可能不在樹上;
2,思路
PAT_甲級_1143 Lowest Common Ancestor (30point(s)) (C++)【BST建構/尋找LCA/倍增法】
好像是一模一樣的題目。。。
3,AC代碼
終于體會到手指在鍵盤上飛舞的快感了!
#include<bits/stdc++.h>
using namespace std;
int N, M, in[10005], key;
struct node{
int key, father, level;
}pre[10005];
void createTree(int root, int left, int right, int father, int level){
if(left > right) return;
pre[root] = {pre[root].key, father, level};
int i = left;
while(i <= right && pre[root].key != in[i])
i++;
createTree(root+1, left, i-1, root, level+1);
createTree(root+(i-left)+1, i+1, right, root, level+1);
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
scanf("%d%d", &M, &N);
for(int i = 0; i < N; i++)
scanf("%d", &in[i]);
for(int i = 0; i < N; i++){
scanf("%d", &key);
pre[i] = {key, -1, -1};
}
createTree(0, 0, N-1, -1, 1);
while(M--){
int a, b, A = N, B = N;
scanf("%d%d", &a, &b);
for(int i = 0; i < N; i++){
if(pre[i].key == a)
A = i;
if(pre[i].key == b)
B = i;
}
if(A == N && B == N)
printf("ERROR: %d and %d are not found.\n", a, b);
else if(A == N)
printf("ERROR: %d is not found.\n", a);
else if(B == N)
printf("ERROR: %d is not found.\n", b);
else{
bool flag = true;
if(pre[A].level < pre[B].level){
flag = false;
swap(A, B);
}
while(pre[A].level > pre[B].level)// !!!大于号
A = pre[A].father;
if(pre[A].key == pre[B].key)
printf("%d is an ancestor of %d.\n", flag ? b : a, flag ? a : b);
else{
while(pre[A].key != pre[B].key){
A = pre[A].father;
B = pre[B].father;
}
printf("LCA of %d and %d is %d.\n", a, b, pre[A].key);
}
}
}
return 0;
}
4,解題過程
一發入魂o(* ̄▽ ̄*)ブ