今天早上模拟赛有一道题，$n,q\le 2\times 10^5$，其余的所有输入都小于等于 $n$，然后我发现有这样一份代码跑得飞快：

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

const int N = 2e5 + 10;
int n, q;
int clk, sz[N], son[N], fa[N], dep[N], dfn[N], top[N];
int id, head[N << 1], to[N << 1], nxt[N << 1];
int ans, col[N], tag;

void add(int u, int v){
	to[++id] = v;
	nxt[id] = head[u], head[u] = id;
}

void dfs(int u, int father){
	sz[u] = 1;
	for(int i=head[u];i;i=nxt[i]){
		int v = to[i];
		if(v == father)
			continue;
		fa[v] = u, dep[v] = dep[u] + 1;
		dfs(v, u);
		sz[u] += sz[v];
		if(!son[u] || sz[v] > sz[son[u]])
			son[u] = v;
	}
}

void build(int u, int t){
	top[u] = t, dfn[u] = ++clk;
	if(son[u])
		build(son[u], t);
	for(int i=head[u];i;i=nxt[i]){
		int v = to[i];
		if(v == fa[u] || v == son[u])
			continue;
		build(v, v);
	}
}

int LCA(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])
			swap(u, v);
		u = fa[top[u]];
	}
	return (dep[u] < dep[v] ? u : v);
}

int dis(int u, int v){
	return dep[u] + dep[v] - 2 * dep[LCA(u, v)] - 1;
}

void impossible(int u, int now){
	col[u] = tag;
	if(!now)
		return ;
	for(int i=head[u];i;i=nxt[i]){
		int v = to[i];
		if(col[v] == tag)
			continue;
		impossible(v, now - 1);
	}
}

void possible(int u, int fa, int now){
	ans = max(ans, now);
	for(int i=head[u];i;i=nxt[i]){
		int v = to[i];
		if(v == fa || col[v] == tag)
			continue;
		possible(v, u, now + 1);
	}
}

int query(int u, int v, int stv){
	ans = 0, ++tag;
	impossible(v, stv);
	possible(u, 0, 0);
	return ans;
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 1);
	build(1, 1); 
	while(q--){
		int a, b, k;
		scanf("%d%d%d", &a, &b, &k);
		int d = dis(a, b);
		if(k < d){
			printf("%d\n", k & 1);
			continue;
		}
		else if(k >= 2 * d + (d & 1)){
			if(d & 1)
				printf((k & 1) ? "1\n" : "-1\n");
            else
            	printf((k & 1) ? "2\n" : "0\n");
		}
		else{
			if((k & 1) && (d & 1))
                printf("1\n");
            else if(!(k & 1) && !(d & 1))
                printf("0\n");
			else if((k & 1) && !(d & 1)){//后手尝试逃跑 
                if(query(b, a, k / 2 + 1) >= k / 2)
                    printf("1\n");
				else
                    printf("2\n");
            }else{//先手试图逃跑 
                if(query(a, b, k / 2) >= k / 2)
                    printf("0\n");
				else
                    printf("-1\n");
            }
		}
	}
	return 0;
}

我很好奇它的 $impossible$ 函数和 $possible$ 函数的复杂度不是 $O(n)$ 的吗？还是说这题 $O(nq)$ 撵过 $2\times 10^5$ 是因为数据太水？