[CF 519E] A and B and Lecture Rooms

這題真是蠻容易想錯的XD

作法：

設要查詢的兩個數是 x , y ，首先可以知道如果 x 走到 y 的步數是奇數，那麼無解，因為從 x 開始的任何一條路徑都是先經過部分的(或沒有) xy 之間的路徑再分岔出去(或沒有分岔)，奇偶性會矛盾。

設 x 走到 y 的路徑是 a_0=x , a_1 , ... , a_(2d)=y ，那麼原題的答案就是把原本的樹砍掉 a_(d-1)a_d 和 a_d a_(d+1) 這兩條邊之後，x 和 y 都不在的那個連通塊的大小，這還必須多討論 a_d 恰好就是 x 和 y 的 LCA 的情況，蠻容易寫錯的。

另外有可能 x 和 y 在同一點，原本一小時內就把這題寫完了，但到最後才突然想到這個情況才AC ......

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn] ;
 
int anc[20][maxn] ;
int dep[maxn],size[maxn] ;
 
void dfs(int x,int f)
{
    anc[0][x]=f ; size[x]=1 ;
    for(auto i : v[x]) if(i!=f)
    {
        dep[i]=dep[x]+1 ;
        dfs(i,x) ;
        size[x]+=size[i] ;
    }
}
 
int n ;
void build()
{
    for(int i=1;i<20;i++) for(int j=1;j<=n;j++)
        anc[i][j]=anc[i-1][anc[i-1][j]] ;
}
 
int query_fa(int x,int d)
{
    if(!d) return x ;
    for(int i=19;i>=0 && d;i--) if(d&(1<<i))
    {
        x=anc[i][x] ;
        d^=(1<<i) ;
    }
    return x ;
}
 
int LCA(int x,int y)
{
    if(dep[x]!=dep[y]) return
        dep[x]>dep[y] ? LCA(query_fa(x,dep[x]-dep[y]),y) :
                        LCA(x,query_fa(y,dep[y]-dep[x])) ;
    if(x==y) return x ;
    for(int i=19;i>=0;i--) if(anc[i][x]!=anc[i][y])
        x=anc[i][x] , y=anc[i][y] ;
    return anc[0][x] ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    dep[1]=0 ;
    dfs(1,1) ;
    build() ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        int f=LCA(x,y) ;
        if(x==y) printf("%d\n",n) ;
        else if((dep[x]+dep[y])%2) printf("0\n") ;
        else if(dep[x]==dep[y])
        {
            int d=dep[x]-dep[f] ;
            int x1=query_fa(x,d-1) , y1=query_fa(y,d-1) ;
            printf("%d\n",n-size[x1]-size[y1]) ;
        }
        else
        {
            int d=(dep[x]+dep[y])/2-dep[f] ;
            int f1,f2 ;
            if(dep[x]>dep[y]) f1=query_fa(x,d-1) ;
            else f1=query_fa(y,d-1) ;
            f2=anc[0][f1] ;
            printf("%d\n",size[f2]-size[f1]) ;
        }
    }
}