1. 图论:

   删除环上点 $S$ 及相关边后，剩余图为森林。其连通块个数满足公式：

   • $\text{连通块个数} = \text{剩余点数} - \text{剩余边数}$

2. 公式应用：

   $S$：环上的点集

   $|S|$：环上点的个数

   $A$：环上边的个数，满足 $|S| = A + 1$

   $E_{\text{del}}$：删除的边数

   结合森林公式推导：

   • 剩余点数 = $n - |S|$

   • 剩余边数 = 总边数 $- E_{\text{del}} = (n-1) - E_{\text{del}}$

   • 连通块个数 = $(n - |S|) - [(n-1) - E_{\text{del}}] = E_{\text{del}} - |S| + 1$

   进一步推导 $E_{\text{del}}$：

   $\text{sum\_deg}_S$：$S$ 中所有点的度数和。

   环上内部边数为 $A$，每条内部边被 $S$ 中两点各计数一次，外部边（一端在 $S$）仅计数一次。因此：

   • $\text{sum\_deg}_S = 2 \times \text{内部边数} + \text{外部边数} = 2A + (E_{\text{del}} - A) = A + E_{\text{del}}$

   • $⇒$ $E_{\text{del}} = \text{sum\_deg}_S - A$

   代入连通块个数公式：

   • $⇒\text{ans} = (\text{sum\_deg}_S - A) - (A + 1) + 1 = \text{sum\_deg}_S - 2A$

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define MAXN 1000005
#define LOG 25
int n,q;
vector<int> g[MAXN];
int dep[MAXN],st[MAXN][LOG];
int deg[MAXN],sum[MAXN];
int lg[MAXN];
void dfs(int u,int pre)
{
	dep[u]=dep[pre]+1;
	st[u][0]=pre;
	sum[u]=sum[pre]+deg[u];
	for(int i=1;i<=lg[dep[u]];i++) st[u][i]=st[st[u][i-1]][i-1];
	for(int v:g[u]) if(v!=pre) dfs(v,u);
}
int get_lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=lg[dep[u]];i>=0;i--)
	{
		if(dep[u]-(1<<i)>=dep[v]) u=st[u][i];
	}
	if(u==v) return u;
	for(int i=lg[dep[u]];i>=0;i--)
	{
		if(st[u][i]!=st[v][i]) u=st[u][i],v=st[v][i];
	}
	return st[u][0];
}
signed main()
{
	FAST_IO;
	//freopen("easy.in","r",stdin);
	//freopen("easy.out","w",stdout);
	cin>>n>>q;
	lg[1]=0;for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y),g[y].push_back(x);
		deg[x]++,deg[y]++;
	}
	dfs(1,0);
	while(q--)
	{
		int u,v;
		cin>>u>>v;
		int lca=get_lca(u,v);
		int deg_sum=sum[u]+sum[v]-2*sum[lca]+deg[lca];
		int cnt=dep[u]+dep[v]-2*dep[lca];
		int ans=deg_sum-2*cnt;
		cout<<ans<<'\n';
	}
	return 0;
}

显然答案是路径上所有点的（度数减二）加起来再加二。 理由是形成环后环上每个点的不在环上的出边都会形成一个连通块。加的二是新边。 随便选个你喜欢的 lca 方式实现即可。时间复杂度 $O((m+q)log n)$。

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无 BUG
 */

/*
 * @Description: I want to be the weakest vegetable in the world!
 * @Author: I.Z.
*/
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
mt19937 sd(random_device{}());
int qpow(int a,int b,int m=MOD,int res=1){
	a%=m;
	while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
	return res;
}
int exgcd(int x,int y,int &a,int &b){
	if(y==0){
		a=1;b=0;
		return x;
	}
	int d=exgcd(y,x%y,a,b);
	int z=b;
	b=a-b*(x/y);
	a=z;
	return d;
}
int _x_,_y_;
inline int inverse(int x,int y=MOD){
	exgcd(x,y,_x_,_y_);
	return (_x_+y)%y;
}
int fac[2000005],inv[2000005];
void init(int n){
	fac[0]=inv[0]=1;
	REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
	inv[n]=qpow(fac[n],MOD-2);
	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int binom(int x,int y){
	return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
char buf[1000000],*p1=buf,*p2=buf;
template<typename T>
void read(T &x){
	x=0;
	int f=1;char c=getchar();
	while(c<48||c>57){
		if(c=='-')f=-f;
		c=getchar();
	}
	while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y){read(x);read(y...);}
int n,q;
vector<int>v[1000005];
int st[21][1000005];
int dfn[1000005],fa[1000005],dep[1000005];
int tot;
int ps[1000005];
void dfs(int x,int pre,int d){
	st[0][dfn[x]=tot++]=fa[x]=pre;dep[x]=d;
	ps[x]+=v[x].size()-2;
	for(auto i:v[x])if(i!=pre)ps[i]=ps[x],dfs(i,x,d+1);
}
int getmax(int x,int y){
	return dep[x]<dep[y]? x:y;
}
int getlca(int x,int y){
	if((x=dfn[x])>(y=dfn[y]))swap(x,y);
	int s=__lg(y-(++x)+1);
	return getmax(st[s][x],st[s][y-(1<<s)+1]);
}
void Main(){
	read(n,q);
	REP(i,1,n){
		int x,y;
		read(x,y);
		--x,--y;
		v[x].pb(y);v[y].pb(x);
	}
	dfs(0,-1,0);
	REP(j,0,__lg(n-1)){
		REP(i,1,n-(1<<(j+1))+1){
			st[j+1][i]=getmax(st[j][i],st[j][i+(1<<j)]);
		}
	}
	while(q--){
		int x,y;
		read(x,y);
		--x,--y;
		int l=getlca(x,y);
		cout<<ps[x]+ps[y]-ps[l]-(l? ps[fa[l]]:0)+2<<'\n';
	}
}
void TC() {
    int tc=1;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	//freopen("easy.in","r",stdin);
	//freopen("easy.out","w",stdout);
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */