闭路 题解

嗯，就是建议降黄。但是我奶不会 lca 所以不会，嗯。

别看题目很复杂，但是看懂了就很显然。

显然环的长度就是树上两点之间的距离加一，而两点距离就是 $\text{dep}[x]+\text{dep}[y]-2\text{dep}[\text{lca}(x,y)]$，不论根为多少。

所以我们直接掏出 lca 板子即可，为了裝🖊️我的板子是用树剖实现的。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n, m;
class tree_spliter{
	private:
	
	vector <vector <int>> edges;
	vector <int> dfn, dep, father, head, rank, son, siz;
	int n;
	void dfs(int cur, int fa){
		father[cur] = fa;
		siz[cur] = 1;
		dep[cur] = dep[fa] + 1;
		for(int i:edges[cur]){
			if(i == fa) continue;
			dfs(i, cur);
			siz[cur] += siz[i];
			if(siz[son[cur]] < siz[i]) son[cur] = i;
		}
	}
	
	void dfs2(int cur, int top, int &curdfn){
		head[cur] = top;
		curdfn++;
		dfn[cur] = curdfn;
		rank[curdfn] = cur;
		if(!son[cur]) return;
		dfs2(son[cur], top, curdfn);
		for(int i:edges[cur]){
			if(i != son[cur] && i != father[cur]) dfs2(i, i, curdfn);
		}
	}
	
	public:
	
	tree_spliter(){}
	
	void init(int n, int k, vector <vector <int>> v){
		this -> n = n;
		edges = v;
		dfn.resize(n + 1);
		father.resize(n + 1);
		son.resize(n + 1);
		siz.resize(n + 1);
		head.resize(n + 1);
		rank.resize(n + 1);
		dep.resize(n + 1);
		dfs(k, 0);
		int curdfn = 0;
		dfs2(k, k, curdfn);
	}
	
	int lca(int x, int y){
		while(head[x] != head[y]){
			if(dep[head[x]] < dep[head[y]]) y = father[head[y]];
			else x = father[head[x]];
		}
		return (dep[x] < dep[y] ? x : y);
	}
	
	int len(int x, int y){
		int l = lca(x, y);
		return dep[x] + dep[y] - 2 * dep[l];
	}
}t;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	vector <vector <int>> v(n + 1);
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	t.init(n, 1, v);
	cin >> m;
	while(m--){
		int x, y;
		cin >> x >> y;
		cout << t.len(x, y) + 1 << '\n';
	}

	return 0;
}

时间复杂度：$O(q\log n)$。