第五章 树 24 AcWing 1636. 最低公共祖先

第五章 树 24 AcWing 1636. 最低公共祖先

原题链接

AcWing 1636. 最低公共祖先

算法标签

LCA

思路

根据前序遍历序列与中序遍历序列构建树, 值得一提的是，在构建过程中， 需要记录每个节点深度， 供后续查找最低公共祖先使用
根据两节点u, v深度，向上查找最低公共祖先
若节点u深度>节点v深度 节点u向上查找(即使u变为u的父节点)
若节点u深度<节点v深度 节点v向上查找(即使v变为v的父节点)
若节点u深度=节点v深度且u!=v 节点u, v同时向上查找(即使u变为u的父节点, v变为v的父节点)
若节点u深度=节点v深度且u=v 此时节点u(v)即为最低公共祖先
时间复杂度分析
对于每次操作， 时间复杂度为O（N）, M次操作时间复杂度O（N*M）时间限制为0.2s， 存在超时风险

卡常数问题如何优化

虽然hash表查询理论时间复杂度为$O（1）$， 但是常数较大。 特别对于该题而言， 由于所有结点权值均在 int 范围内（范围过大），进行1000次查询（查询次数多）， 需要耗费较多时间。
若是将所有结点权值均由int 范围内映射化至大小为N的数组中， 缩小了查找范围，同时， 数组采用下标为索引查询理论时间复杂度为O（1）， 虽说与hash表查询理论时间复杂度为O（1）一致， 但是常数远小于hash表。每次对于根节点的查询操作可以耗费较少的时间

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
#define int long long
#define x first
#define y second
#define ump unordered_map
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pair PII;
const int N = 100005;
int n, m;
int in[N], pre[N], seq[N];
ump pos;
int f[N], d[N];
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
int build(int il, int ir, int pl, int pr, int dd){
    int root=pre[pl];
    int k=root;
    d[root]=dd;
    if(k>il){
        f[build(il, k-1, pl+1, k-1-il+pl+1, dd+1)]=root;
    }
    if(k