loj10135.「一本通 4.4 练习 2」祖孙询问

SLOJ P10135. 「一本通 4.4 练习 2」祖孙询问

题目描述

已知一棵n个节点的有根树。有m个询问，每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。

输入格式

输入第一行包括一个整数n表示节点个数；

接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是−1，那么a就是树的根；

第n+2行是一个整数m表示询问个数；

接下来m行，每行两个正整数x和y，表示一个询问。

输出格式

对于每一个询问，若x是y的祖先则输出1，若y是x的祖先则输出2，否则输出0。

输入数据 0

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出数据 0

1
0
0
0
2

数据范围与提示

对于30%的数据，1≤n,m≤10³；

对于100%的数据，1≤n,m≤4×10⁴，每个节点的编号都不超过4×10⁴。

思路：明显就是一道纯粹的LCA（按照惯例恶补一波），只不过判断这两点间的距离与任意一点到LCA的距离作比较，若大于，则无关，若等于，则有关，等于时再判断一下哪个深度大就是儿子。

证明：因为当两点分别在不同子树上时，两点间的距离即为两点分别到LCA的距离之和，若两点中有一点为另一点祖宗，那么两点间的距离即为深度大的那一点到祖宗的距离，所以相等时有关系，深度大的为儿子。

两点间的距离不可能小于两点分别到LCA的距离的和。

#include<bits/stdc++.h>
using namespace std;
int f[100010][20],vis[100010],dis[100010],n,q,rt;
vector<int>g[100010];
void dfs(int x,int d){
    vis[x] = 1;
    dis[x] = d;
    for(int i = 1;(1<<i)<=dis[x];i++)
        f[x][i] = f[f[x][i-1]][i-1];
    for(int i = 0;i<g[x].size();i++){
        int v = g[x][i];
        if(vis[v])continue;
        f[v][0] = x;
        dfs(v,d+1);
    }
} 
int lca(int x,int y){
    if(dis[x]<dis[y])swap(x,y);
    int k = dis[x]-dis[y];
    for(int i = 0;(1<<i)<=k;i++)
        if(k&(1<<i))
            x = f[x][i];
    if(x==y)return x;
    for(int i = 19;i>=0;i--){
        if(f[x][i]!=f[y][i])
            x = f[x][i],y = f[y][i];
    }
    return f[x][0];
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(v==-1){
            rt = u;
            continue;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(rt,0);
    scanf("%d",&q);
    for(int i = 1;i<=q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        int tmp = lca(x,y);
        if(dis[x]+dis[y]-2*dis[tmp]>dis[x]-dis[tmp]&&dis[x]+dis[y]-2*dis[tmp]>dis[y]-dis[tmp]){
            puts("0");
        }else if(dis[x]>dis[y]){
            puts("2");
        }else{
            puts("1");
        }
    }
    return 0;
}

综上所述，我是蒟蒻

2022-10-27 16:40:35