论本题数据都卡了什么算法

显然，下面的代码是 $O(nm)$ 的。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> v[500005];
int dep[500005], father[500005];
bool vis[500005];
int n, m;
void dfs(int cur, int fa){
	dep[cur] = dep[fa] + 1;
	father[cur] = fa;
	for(int i:v[cur]){
		if(i == fa) continue;
		dfs(i, cur);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	while(m--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int idx;
			cin >> idx;
			vis[idx] = 1;
		}else{
			int x, y;
			cin >> x >> y;
			if(dep[x] > dep[y]) swap(x, y);
			int ans = 0, ct = 0;
			while(dep[y] > dep[x]) y = father[y], ans++, ct += vis[y];
			while(x != y){
				x = father[x], y = father[y];
				ans += 2;
				if(x == y) ct += vis[x];
				else ct += vis[x] + vis[y];
			}
			cout << ans - ct << '\n';
		}
	}
	
	return 0;
}