祖孙询问 用欧拉序列转化为 RMQ 问题

本文主要是介绍祖孙询问 用欧拉序列转化为 RMQ 问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 分析

N 个点，按照欧拉序给它们排序到一个数组里（数组长度是2*（N-1） + 1 = 2*N-1），并标记每个节点第一次出现的位置，st表处理欧拉序节点的最小深度。

查询（u，v） 找到两个节点第一次所在的位置，再从st表中找到这两个位置间的最小深度。

欧拉序：每经过一次该节点记录一次该序列

dfs序：记录入栈和出栈的序列

dfn序：只记录入栈的序列

dfs 预处理出每个节点的深度 dep[u]
第一次遍历到这个节点在第几步 first[u]
第几步遍历到哪个节点（考虑回溯）a[i]

lca(a,b) 一定为 first[a]到 first[b] 之间遍历过的深度最小的点

预处理出 a[i] 之后即可预处理 stst 表存储第 i 步及之后的 2j 步遍历到的深度最小的节点

对于每个 lca 询问，我们都可以转化为 st 表中区间最小数的查询，即可实现 O(1) 问答

//-------------------------代码----------------------------

//#define int ll
const int N = 40010, M = N * 2;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;
int root;

int dep[N], dfn[N], step;       //  dfn[u]表示首次遍历到u号节点是第几步
int a[M];                       //  a[i]表示第i步遍历到的节点编号

void dfs(int u,int fa) {
    dfn[u] = ++ step;
    a[step] = u;
    for(int i = h[u];~i;i=ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        dep[j] = dep[u] + 1;
        dfs(j,u);
        a[++step] = u;
    }
}

int f[M][17];
void init() {
    for(int j = 0; j < 17 ; j++) {
        for(int i = 1;i + (1<<j) - 1 <= n * 2;i ++ ) {
            if(!j) f[i][j] = a[i];
            else {
                if(dep[f[i][j-1]] < dep[f[i+(1<<j-1)][j-1]]) f[i][j] = f[i][j-1];
                else f[i][j] = f[i+(1<<j-1)][j-1];
            }
        }
    }
}

int query(int l,int r) {
    if(l > r )swap(l,r);
    int k = log2(r-l+1);
    int a = f[l][k],b = f[r - (1<<k) + 1][k];
    if(dep[a] < dep[b])return a;
    else return b;
} 

int lca(int a,int b) {
    return query(dfn[a],dfn[b]);
}

void solve()
{
    cin>>n;
    ms(h,-1);
    ms(dfn,0x3f);
    
    fo(i,1,n) {
        int a,b;cin>>a>>b;
        if(b == -1)root = a;
        else add(a,b),add(b,a);
    }
    
    dep[root] = 1;
    dfs(root,-1);
    init();
    
    cin>>m;
    fo(i,1,m) {
        int a,b;cin>>a>>b;
        int t = lca(a,b);
        if(t == a) puts("1");
        else if(t == b) puts("2");
        else puts("0");
    }
    rt;
}

signed main(){
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

这篇关于祖孙询问 用欧拉序列转化为 RMQ 问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！