[ABC014D] 閉路 [LCA]

现有一棵 \(N(N\le 10^5)\) 个节点的树，保证节点编号为 \(1\to N\)。首先输入 \(N\)，然后输入 \(N-1\) 条边。

然后输入一个整数 \(q(q\le 10^5)\)。

接下来给出 \(q\) 次询问。

对于每次询问，会给出两个整数 \(x,y\)，请输出一行若在 \(x,y\) 之间连边，包含这条边的环包含多少条边。保证在此之前 \(x, y\) 没有边直接相连。

由此问题便可以转为LCA问题进行解决

key code

// Problem: [ABC014D] 閉路
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_abc014_4
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-falign-functions,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3,2)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<tuple>
#include<cstdio>
#include<time.h>
#include<cstring>
#include<ostream>
#include<numeric>
#include<limits.h>
#include<iostream>
#include<iterator>
#include<algorithm>
#include<functional>
#include<unordered_map>
#include<unordered_set>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using i64=long long;
#define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define puts(res) cout<<res<<'\n'
#define put cout<<'\n'
#define cout(a) cout<<a<<'\n';
#define debug(a) cout<<#a<<"="<<a<<endl
#define debug2(a,b) cout<<#a<<"="<<a<<" "<<#b<<"="<<b<<endl
#define debug3(a,b,c) cout<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<endl
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define mem(a) memset(a,0x3f,sizeof(a))
#define fup(o,a,b) for(int o=a;o<=b;o++)
#define up(a,b) for(int o=a;o<=b;o++)
#define dn(a,b) for(int o=a;o>=b;o--)
#define fdn(o,a,b) for(int o=a;o>=b;o--)
#define show(a) for(auto it:a)cout<<it<<" ";
#define cvec(a) for(auto &it:a)cin>>it;
#define sz(v) (int)v.size()
#define all(a) (a).begin(),(a).end()
#define rall(x) (x).rbegin(), (x).rend()
#define YES {puts("YES");return;}
#define NO {puts("NO");return;}
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define endl '\n'
#define fi first
#define se second
#define pb emplace_back
#define pob pop_back
#define pof pop_front
#define pf emplace_front
#define db double
#define MAX 0x7ffffffffffffffff
#define INF 0x3f3f3f3f3f3f3f3f
const int N=1e5+10;
const int M=35;//M开小了会WA
int n,m;
int h[N],e[N<<1],ne[N<<1],idx;
int fa[N][M];
int dep[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int f){
	fa[u][0]=f;dep[u]=dep[f]+1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==f)continue;
		dfs(j,u);
	}
}
void dp(){
	fup(j,1,M-1){
		fup(i,1,n){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
}
int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    fdn(k,M-1,0){
        if(dep[fa[a][k]]>=dep[b])a=fa[a][k];
    }
    if(a==b)return a;
    fdn(k,M-1,0){
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
void solve(){
	//try it again.
	cin>>n;
	mem1(h);
	up(1,n-1){
		int a,b;
		cin>>a>>b;
		add(a,b);add(b,a);
	}
	cin>>m;
	dfs(1,0);dp();
	up(1,m){
		int a,b;
		cin>>a>>b;
		int root=lca(a,b);
		cout<<dep[a]+dep[b]-2*dep[root]+1<<endl;
	}
}
signed main(){
	IOS;
	// int __;
	// cin>>__;
	// while(__--)
		solve();
    return 0;
}