A1151.md

A1151 LCA in a Binary Tree

1.题意理解

经典LCA问题又来了嗷

2.思路分析

哟呵，这不给了中序+先序？套板子建树！然后就会超时。。。

其实把建树的板子稍微改改，就能把这事办了。

3.参考代码

#include<bits/stdc++.h>
using namespace std;

vector<int> in, pre;
unordered_map<int, int> in_pos, flag;

int ans = -1;
void lca(int u, int v, int preL, int preR, int inL, int inR)
{
    if(preL > preR || inL > inR)
        return;

    int pos_u = in_pos[u], pos_v = in_pos[v];

    int root = inL;
    while(in[root] != pre[preL]) inL++;
    int numL = root - inL;

    if((pos_u <= root && root <= pos_v) || (pos_v <= root && root <= pos_u))
        ans = in[root];
    if(pos_u < root && pos_v < root)
        lca(u, v, preL + 1, preL + numL, inL, root - 1);
    if(pos_u > root && pos_v > root)
        lca(u, v, preL + numL + 1, preR, root + 1, inR);
}


int main()
{
    int m, n, x, u, v;

    scanf("%d%d", &m, &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        in.push_back(x);
        flag[x] = 1;
        in_pos[x] = i;
    }
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        pre.push_back(x);
    }

    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &u, &v);
        if(!flag[u] && !flag[v]) printf("ERROR: %d and %d are not found.\n", u, v);
        else if(!flag[u]) printf("ERROR: %d is not found.\n", u);
        else if(!flag[v]) printf("ERROR: %d is not found.\n", v);
        else
        {
            lca(u, v, 0, n - 1, 0, n - 1);
            if(ans == u) printf("%d is an ancestor of %d.\n", u, v);
            else if(ans == v) printf("%d is an ancestor of %d.\n", v, u);
            else printf("LCA of %d and %d is %d.\n", u, v, ans);
        }
    }

    return 0;
}