C++ 解法, 执行用时: 1157ms, 内存消耗: 94316K, 提交时间: 2022-02-19 08:26:16

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

int n,Q;
int dep[MAXN],f[MAXN][25];
vector<int>G[MAXN];
void dfs(int now , int fa){
	f[now][0] = fa , dep[now] = dep[fa] + 1;
	for(auto v : G[now]){
		if(v == fa)continue;
		dfs(v , now);
	}
}

int lca(int x , int y){
	if(dep[x] < dep[y])swap(x , y);
	int dx = dep[x] - dep[y];
	for(int i = 0 ; i <= 20 ; i++)if(dx & (1ll << i))x = f[x][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 dis(int x , int y){
	return dep[x] + dep[y] - 2 * dep[lca(x , y)];
}

int main(){
	scanf("%d%d" , &n , &Q);int x,y;
	for(int i = 1 ; i < n ; i++){
		scanf("%d%d" , &x , &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1 , 1);
	for(int j = 1 ; j <= 20 ; j++)
		for(int i = 1 ; i <= n ; i++)
			f[i][j] = f[f[i][j - 1]][j - 1];
	int tp;
	int u = 1,v = 1,maxl = 0;
	for(int i = 2 ; i <= n ; i++)if(dis(u , i) > dis(u , v))v = i;
	for(int i = 1 ; i <= n ; i++)if(dis(i , v) > dis(u , v))u = i;
	maxl = dis(u , v);
	while(Q--){
		scanf("%d" , &tp);
		if(tp == 1){
			scanf("%d" , &x);
			n++ , f[n][0] = x , dep[n] = dep[x] + 1;
			for(int j = 1 ; j <= 20 ; j++)f[n][j] = f[f[n][j - 1]][j - 1];
			if(dis(u , v) < dis(u , n))v = n;
			if(dis(u , v) < dis(v , n))u = n;
			maxl = dis(u , v);
		}
		else{
			scanf("%d%d" , &x , &y);
			//判断与直径相关大小
			int A,B;
			A = dis(u , y) , B = dis(v , y);
			if(A < B)swap(A , B) , swap(u , v);
			int C , D;
			C = maxl - A , D = maxl - C;
			if(D - C > x)cout<<1<<endl;
			else cout<<0<<endl;
		}
	}
}