题解

Difficulty：4.8 / Medium-

Tag：LCA，启发式合并，树的直径

显然题目指的就是会连成一个森林。

首先考虑静态树如何查询。

显然，离一个点最远的点是树任意一个直径的两端点。所以找到直径两端点然后 LCA 即可 $O(q\log n)$。

然后考虑讲一个点加入树后，直径有何变化。根据上面的结论，直径要么不变，要么一端变为这个点。

所以我们合并时大小小的树逐个加入到大小大的点即可。

这么做要想让原来的树被合并，新的树得更大才行。所以这样显然最多修改 $O(n\log n)$ 个节点（应该吧）。

然后如果你的常数和我一样的话，注意卡常（其实不用卡多少，进行一些简单的优化比如说 vector 换成静态数组即可）。

namespace cjdst{
    class Tree{
		std::vector <std::vector <int>> v;
		int father[300005][21];
		// std::vector <std::vector <int>> father;
		std::vector <int> dep;
		std::vector <int> root;
		std::vector <int> siz;
		std::vector <int> dx, dy;
		
		int get_lca(int x, int y){
			if(dep[x] < dep[y]) std::swap(x, y);
			for(int i = 18; i >= 0; i--){
				if(dep[father[x][i]] >= dep[y]) x = father[x][i];
			}
			if(x == y) return x;
			for(int i = 18; i >= 0; i--){
				if(father[x][i] != father[y][i]){
					x = father[x][i], y = father[y][i];
				}
			}
			return father[x][0];
		}
		
		int get_len(int x, int y){
			int lca = get_lca(x, y);
			return dep[x] + dep[y] - 2 * dep[lca];
		}
		
		void dfs(int cur, int fa, int rt, std::vector <int> &nodes){
			nodes.push_back(cur);
			root[cur] = rt;
			dep[cur] = dep[fa] + 1;
			father[cur][0] = fa;
			for(int i = 1; i <= 18; i++){
				father[cur][i] = father[father[cur][i - 1]][i - 1];
			}
			for(int i:v[cur]){
				if(i == fa) continue;
				dfs(i, cur, rt, nodes);
			}
		}
		
		public:
		
		Tree(){}
		Tree(int n){
			v.resize(n + 5);
			// father.resize(n + 5, std::vector <int>(19));
			root.resize(n + 5);
			siz.resize(n + 5, 1); 
			dep.resize(n + 5);
			dx.resize(n + 5);
			dy.resize(n + 5);
			for(int i = 1; i <= n; i++){
				root[i] = i;
				dx[i] = dy[i] = i;
				for(int j = 0; j <= 18; j++){
					father[i][j] = i;
				}
			}
		}
		
		void merge(int x, int y){
			v[x].push_back(y), v[y].push_back(x);
			if(siz[root[x]] < siz[root[y]]) std::swap(x, y);
			siz[root[x]] += siz[root[y]];
			std::vector <int> nodes;
			dfs(y, x, root[x], nodes);
			int rt = root[x];
			for(int i:nodes){
				int d0 = get_len(dx[rt], dy[rt]), d1 = get_len(dx[rt], i), d2 = get_len(dy[rt], i);
				if(d1 <= d0 && d2 <= d0) continue;
				if(d1 > d0){
					if(d2 > d1) dx[rt] = i;
					else dy[rt] = i;
				}else if(d2 > d0) dx[rt] = i;
			}
		}
		
		int query(int cur){
			int rt = root[cur];
			return std::max(get_len(dx[rt], cur), get_len(dy[rt], cur));
		}
	};

	void solve(){
		int c, n, m;
		std::cin >> c >> n >> m;
		Tree tr(n);
		int lastans = 0;
		for(int _ = 1; _ <= m; _++){
			int tmp;
			std::cin >> tmp;
			if(tmp == 1){
				int x, y;
				std::cin >> x >> y;
				if(c) x ^= lastans, y ^= lastans;
				tr.merge(x, y);
			}else{
				int x;
				std::cin >> x;
				if(c) x ^= lastans;
				lastans = tr.query(x);
				std::cout << lastans << '\n';
			}
		}
	}
}

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