题解 CF519E 【A and B and Lecture Rooms】

CF519E 【A and B and Lecture Rooms】

前言:

你可能需要用到的前置知识点: 倍增求 $LCA$ (或者说是树上倍增？)

正文

题目大意:

给定一棵树，以及 $m$ 个询问，每次询问的形式是给定两个点 $x,y$ ，求有多少个点 $u$ 满足 $dis(u,x) == dis(u,y)$

题目不难，但是要分类讨论清楚也不是那么容易。

无根树，我们假定 $1$ 号点为根即可。

下面约定概念:

$dep[x]$ 表示 $x$ 点的深度。 $siz[x]$ 表示 $x$ 为根的子树的大小。

然后我们开始分类讨论(下面假定 $dep[x] < dep[y]$ ):

$1$ . $x = y$

输出点的个数即可。所有点均满足条件。

$2$ . $LCA(x,y) = x$

意味着 $x$ 是 $y$ 的祖先节点。

不难发现，倘若 $x$ 到 $y$ 中间有偶数个点的话，是没有答案的，输出 $0$

倘若 $x$ , $y$ 中间有奇数个点，那么答案就是 $x$ 到 $y$ 的路径的中点 $p$ 以及 $p$ 的所有儿子（除了 $p$ 中 $y$ 所在的那一整个子树）。可以通过倍增的方法求出 $p$ 点以及 $p$ 中 $y$ 所在的那一个子树的根节点。

$3.LCA(x,y) != x$ && $dep[x] == dep[y]$

这个说明 $LCA(x,y)$ 就是 $x,y$ 的路径中点，那么除了在以 $LCA(x,y)$ 为根的子树中的 $x$ 所在的子树以及 $y$ 所在的子树，其它的点都可以。

$4$ . $LCA(x,y) != x$ && $dep[x] != dep[y]$

假若路径中有偶数个点，很显然没有答案。

假若是奇数，取路径中点 $p$ 求子树 - $p$ 中 $y$ 所在的那一整个子树大小大小即可。

至于具体写法的一些小 $trick$ 就放在代码里面了。

// Problem: CF519E A and B and Lecture Rooms
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 50;
int start[MAXN] , tot = 0 , siz[MAXN] , n , parent[MAXN][20] , dep[MAXN];

struct Edge {
    int next,to;
} edge[MAXN << 1];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void add(int from,int to) {
    edge[++tot].next = start[from];
    edge[tot].to = to;
    start[from] = tot;
    return ;
}

int DFS(int x , int from) {//预处理Parent数组以及深度数组
    siz[x] = 1; parent[x][0] = from; dep[x] = dep[from] + 1;
    for(int i = 1 ; i <= log2(dep[x]) ; i ++) 
    parent[x][i] = parent[parent[x][i - 1]][i - 1];
    for(int i = start[x] ; i ; i = edge[i].next) {
        int to = edge[i].to;
        if(to == from) continue;
        siz[x] += DFS(to , x);
    }
    return siz[x];
}

int LCA(int x,int y) {//倍增求LCA的模板
    if(dep[x] > dep[y]) swap(x,y);
    for(int i = log2(dep[y] - dep[x]) ; i >= 0 ; i --)
        if(dep[parent[y][i]] >= dep[x]) y = parent[y][i];
    if(x == y) return x;
    for(int i = log2(dep[x]) ; i >= 0 ; i --)
    if(parent[x][i] != parent[y][i]) x = parent[x][i] , y = parent[y][i];
    return parent[x][0];
}

int GetFa(int x,int Deep) {
    //这是给定深度，然后倍增求一个距离 x 点距离为 k 的祖先 
    while(Deep) {
        int d = log2(Deep);
        x = parent[x][d];
        Deep -= (1 << d);
    }
    return x;
}

int GetLas(int x,int Fa) {
    //这是给定一个点，然后倍增求一个点所在这个点中的哪个子树（求所在子树的根）
    for(int i = log2(dep[x]) ; i >= 0 ; i --)
    if(dep[parent[x][i]] > dep[Fa]) x = parent[x][i];
    return x;
}

void solve(int x,int y) {
    if(dep[x] > dep[y]) swap(x , y);
    if(x == y) {printf("%d\n",n); return ;}
    if(LCA(x,y) == x) {
        if((dep[y] - dep[x]) & 1) {printf("%d\n",0); return ;}//这表示是偶数个点可以画图知道
        int Fa = GetFa(y,(dep[y] - dep[x]) >> 1) , son = GetFa(y , ((dep[y] - dep[x]) >> 1) - 1);//这里Fa就是中点
        printf("%d\n",siz[Fa] - siz[son]);
        return ;
    }
    int L = LCA(x,y) , Road = dep[x] + dep[y] - dep[L] * 2;//故意不+1的....
    if(dep[x] - dep[L] == dep[y] - dep[L]) {//对应情况3
        int LS,RS;
        LS = GetLas(x , L) , RS = GetLas(y , L);//分别求出所在的子树
        int Ans = 0;
        Ans = n - siz[LS] - siz[RS];
        printf("%d\n",Ans);
        return ;
    }
    if(Road & 1) {printf("%d\n",0) ; return ;} //偶数个点
    else {
        int Fa = GetFa( y , (Road >> 1)) , son = GetLas(y , Fa);
        printf("%d\n",siz[Fa] - siz[son]);//对应情况4
        return ;
    }
    return ;
}

int main() {
    n = read();
    for(int i = 1 ; i <= n - 1; i ++) {
        int u = read() , v = read();
        add(u , v) ; add(v , u);
    }
    DFS(1,0);
    int Q = read();
    while(Q --) {
        int u = read() , v = read();
        solve(u,v);
    }
    return 0;
}