UOJ #297. 一样远

Description

本题没有背景嘤嘤嘤。

给一棵树以及树上的两个点，问树上到这两个点距离相同的点的个数。
Input

第一行一个整数N代表点的个数。

接下来N-1 行，每行两个数字F和T，表示F和T之间有一条边。

接下来一行一个整数 M 代表询问次数。

接下来 M 行，每行两个数字 A 和 B，表示这次询问 A 和 B（A 可能与 B 相同）。
Output

输出 M 行，每行一个整数表示到 A 和 B 一样远的点个数。
Sample Input

4
1 2
2 3
2 4
2
1 2
1 3

Sample Output

0
2

Hint

10% 的数据，N,M=0

30% 的数据：N,M≤1000；

100% 的数据：1≤N,M≤100000,保证树的形态随机
Time Limit&Memory Limit

Time Limit :1s

Memory Limit : 256M

本题直接找两点的距离中点即可,注意:若两点距离为奇数则无解.
若有中点,将两点跳到中点的子节点,分别即为u,v,当两点深度相同时,ans=n-size[u]-size[v]
当两点深度不同时,ans=size[fa[u]]-size[u](这里定义u为较深的那个节点,fa[u]即为两节点中点).

Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int M=100005;
const int N=17;
int n,m,fa[M][N],dep[M],son[M];
vector<int> G[M];
void dfs(int u){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v!=fa[u][0]){ 
            dep[v]=dep[u]+1;
            fa[v][0]=u;
            for(int j=1;j<17;j++){
                fa[v][j]=fa[fa[v][j-1]][j-1];
            }
            dfs(v);
            son[u]+=son[v];
        }
    }
}
int up(int x,int t){
    for(int i=0;i<17;i++){
        if(t&(1<<i)){
            x=fa[x][i];
        }
    }
    return x;
}
int lca(int u,int v){
    if(dep[u]>dep[v]){
        u=up(u,dep[u]-dep[v]);
    }
    if(u==v){
        return u;
    }
    for(int i=16;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
int result(int u, int v){
    if(u==v){
        return n;
    }
    else{
        if(dep[u]<dep[v]){
            swap(u,v);
        }
        int x=lca(u,v);
        int s=dep[u]+dep[v]-2*dep[x];
        if(s%2==1){
            return 0; 
        }
        if(dep[u]==dep[v]){
            u=up(u,s/2-1);
            v=up(v,s/2-1);
            return n-son[u]-son[v];
        }
        else{
            u=up(u,s/2-1);
            return son[fa[u][0]]-son[u];
        }
    }
}
int main(){
    scanf("%d",&n);
    int u,v;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        son[i]=1;       
    }
    for(int j=0;j<17;j++){
        fa[1][j]=1;
    }
    dep[1]=1;
    dfs(1); 
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        printf("%d\n",result(u,v));
    }
    return 0;
}

UOJ #297. 一样远

原文：https://www.cnblogs.com/ukcxrtjr/p/11503956.html