缩点建新图

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
// 原图
int n;
vector<int> ee[MAXN + 5];
// 所属王国
int id[MAXN + 5];
queue<int> q; // 标王国用到的队列
// 同王国的点缩成一个点后的新图
vector<int> e[MAXN + 5];
// -------start LCA--------
// f[i][j] 记录 i 的 2^j 级别祖先
int f[MAXN + 5][25];
// dep[i] 求节点 i 的深度
int dep[MAXN + 5];
void dfs(int u, int fa)
{
    f[u][0] = fa;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
void init(int s)
{
    dep[s] = 0;
    dfs(s, 0); // 预处理深度 dep[u]，以及一级祖先 f[u][0]
    // i 的 2^j 级别祖先 = i 的 2^{j-1} 级别祖先的 2^{j-1} 级别祖先
    for (int j = 1; (1LL << j) <= n; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = f[f[i][j - 1]][j - 1];
}
// lca(u,v) 返回 u,v 的最近公共祖先
int lca(int u, int v)
{
    // 保证 u 在上面，v 在下面
    if (dep[v] < dep[u])
        swap(u, v);
    // 拉到同样的深度
    for (int j = 20; j >= 0; j--)
        if (dep[v] - dep[u] >= (1 << j))
            v = f[v][j];
    // 初始两点之间是祖孙关系时，拉到同样深度就会变成同一个点
    if (u == v)
        return u;
    // 同步往上走，跳到了 lca 下面一跳位
    for (int j = 20; j >= 0; j--)
        if (f[u][j] != f[v][j])
            u = f[u][j], v = f[v][j];
    return f[u][0];
}
// -------end LCA--------
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        ee[u].push_back(v);
        ee[v].push_back(u);
    }
    // 标所属王国
    for (int i = 1; i <= n; i++)
        if (ee[i].size() > 2)
        {
            id[i] = i;
            q.push(i);
        }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : ee[u])
            if (!id[v])
            {
                id[v] = id[u];
                q.push(v);
            }
    }
    // 建立新图
    for (int u = 1; u <= n; u++)
        for (int v : ee[u])
            if (id[u] != id[v])
                e[id[u]].push_back(id[v]);
    // LCA 初始化
    int root = id[1]; // 1 号点所属王国首都记为根节点
    init(id[1]);
    // Q 次询问
    int Q;
    cin >> Q;
    while (Q--)
    {
        int u, v;
        cin >> u >> v;
        u = id[u];
        v = id[v];
        int uv = lca(u, v);
        cout << dep[u] + dep[v] - 2 * dep[uv] + 1 << "\n";
    }
    return 0;
}

不缩点直接做

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

int n,Q;
int x,y;
int dist[200005],vis[200005],sum[200005],f[200005][25];
queue<int> M;
vector<int> G[200005];

void dfs(int x,int fa){
	dist[x]=dist[fa]+1;
	f[x][0]=fa;
    sum[x]=sum[fa];
    if (vis[fa]!=vis[x])    sum[x]++;
	int siz=(int)G[x].size();
	for (int i=0;i<=siz-1;i++){
		if (fa==G[x][i])	continue;
		dfs(G[x][i],x);
	}
} 

int lca(int x,int y){
	if (dist[x]>dist[y])	swap(x,y);
	for (int i=20;i>=0;i--){
		if (dist[x]+(1LL<<i)<=dist[y])	y=f[y][i];
	}
	if (x==y)	return x; 
	for (int i=20;i>=0;i--){
		if (f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

int main(){
    cin>>n;
	for (int i=1;i<=n-1;i++){
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
    for (int i=1;i<=n;i++){
        if (G[i].size()>=3){
            M.push(i);
            vis[i]=i;
        }
    }
    while (M.size()>0){
        int now=M.front();M.pop();
        int siz=G[now].size();
        for (int i=0;i<siz;i++){
            int nxt=G[now][i];
            if (vis[nxt]==0){
                vis[nxt]=vis[now];
                M.push(nxt);
            }
        }
    }
	dfs(1,0);
    for (int k=1;k<=20;k++){
		for (int i=1;i<=n;i++){
			f[i][k]=f[f[i][k-1]][k-1];
		}
	}
    cin>>Q;
	while (Q--){
		cin>>x>>y;
        int xy=lca(x,y);
        int ans=sum[x]+sum[y]-sum[xy]-sum[f[xy][0]];
        if (vis[xy]==vis[f[xy][0]]) ans++;
        cout<<ans<<'\n';
	}
}