题解 CF519E 【A and B and Lecture Rooms】

· · 题解

经典树上LCA。

luogu原题阅读。

这道题简单地说就是给定树上的两个点x,y。求树上能使得到x,y距离相等的点数。

我们可以分类讨论。

  1. 若LCA到x和LCA到y的距离相等且x,y不是同一个点。
    用总点数n-x这棵子树上的点数-y这棵子树上的点数=到x,y距离相等的点数。

  2. 若LCA到x和LCA到y的距离不相等,且分别为a,b。
    (1)a+b为奇数，则a-b必定为奇数(和差）。
    x,y的距离差必定同时加或减去一个偶数，永远不可能是0。
    (2)a+b为偶数，不妨假设a>b,在a上必有一点距离LCA（a-b)/2到x,y距离相等。设这个点为P，以P为根的子树结点-P到x的结点数+1=到x,y距离相等的点数。

  3. x,y是同一个点.
    树上任何一个点都成立。

上代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;

struct Edge{
    int v,nxt;
}edge[maxn*2];

int head[maxn],tot;
void init() {
    memset(head,-1,sizeof head);
    tot = 0; //下一个等待被用的节点。  
}

void addedge(int u,int v) { //u->v ，边权为w
    edge[tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}

int fa[maxn][20],dep[maxn],siz[maxn];
void dfs(int u,int pre) { //nlogn的预处理
    fa[u][0] = pre;
    siz[u] = 1;
    for(int i=1;i<20;i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];

    dep[u] = dep[pre] + 1;
    for(int i=head[u];i!=-1;i=edge[i].nxt) {
        int v = edge[i].v;
        if(v==pre) 
            continue;
        dfs(v,u);
        siz[u] += siz[v];
    }
}

int LCA(int u,int v) {
    if(dep[u]>dep[v]) 
        swap(u,v);

    for(int i=19;i>=0;i--)
        if(dep[fa[v][i]] >= dep[u])  v = fa[v][i];

    if(u==v) 
        return u;
    for(int i=19;i>=0;i--) {
        if(fa[u][i]==fa[v][i]) 
            continue;
        u = fa[u][i];
        v = fa[v][i];
    }
    return fa[u][0];
}
int jump_up(int u,int k) {
    int i = 0;
    while(k) {
        if(k&1) u = fa[u][i];
        k>>=1;
        i++;
    }
    return u;
}

int n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin>>n;
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    cin>>m;
    dfs(1,0); //nlogn
    while(m--) { //mlogn
        int a,b;
        cin>>a>>b;
        int lca = LCA(a,b);
        if(a==b) {
            cout<<n<<"\n";
        }
        else if(dep[a]==dep[b]) {
            int x =jump_up(a,dep[a]-dep[lca]-1);
            int y = jump_up(b,dep[b]-dep[lca]-1);
            cout<< n - siz[x] -siz[y]<<"\n";
        } else {
            int d = dep[a]+dep[b] -2*dep[lca];
            if(d&1) cout<<"0"<<"\n";       // if (d%2==1)
            else {
                if(dep[a]>dep[b]) swap(a,b);
                int y = jump_up(b,d/2-1);
                int x = fa[y][0];
                cout<<siz[x] - siz[y]<<"\n";
            }
        }
    }

    return 0;
}