欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1143 Lowest Common Ancestor (30分)

程序员文章站 2022-07-14 14:49:27
...

在超时的边缘疯狂试探,注意有样例是u == v且存在于树中。

1143 Lowest Common Ancestor (30分)

#include<vector>
#include<set>
#include<cstdio>
#define maxn 10010
using namespace std;

int pre[maxn];
struct node {
    int data;
    node *left, *right;
};

node* build_tree(int l, int r) {
    if (l >= r) return NULL;
    node* root = new node;
    root->data = pre[l];
    int i;
    for (i = l + 1; i < r; i++) {
        if (pre[i] >= pre[l]) break;
    }
    root->left = build_tree(l + 1, i);
    root->right = build_tree(i, r);
    return root;
}

bool finduv(node* root, int u, int v, bool &ue, bool &ve, int &a) {
    if (root == NULL) return false;
    bool lue = false, lve = false, rue = false, rve = false;
    bool left = finduv(root->left, u, v, lue, lve, a);
    if (left == true) return true;
    bool right = finduv(root->right, u, v, rue, rve, a);
    if (right == true) return true;
    if (u == root->data || lue || rue) ue = true;
    if (v == root->data || rve || lve) ve = true;
    if (ue == true && ve == true) {
        a = root->data;
        return true;
    }
    return false;
}

int main() {
    int M, N;
    scanf("%d %d", &M, &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &pre[i]);
    }
    node* root = build_tree(0, N);
    while (M--) {
        int u, v;
        scanf("%d %d", &u, &v);
        bool ue = false, ve = false;
        int a;
        bool found = finduv(root, u, v, ue, ve, a);
        if (found) {
            if (a == u) {
                printf("%d is an ancestor of %d.\n", u, v);
            }
            else if (a == v) {
                printf("%d is an ancestor of %d.\n", v, u);
            }
            else printf("LCA of %d and %d is %d.\n", u, v, a);
        }
        else {
            if (ue == false && ve == false) printf("ERROR: %d and %d are not found.\n", u, v);
            else if (ue == false) printf("ERROR: %d is not found.\n", u);
            else printf("ERROR: %d is not found.\n", v);
        }
    }

    return 0;
}

 

相关标签: 编程练习 PAT