闰土

倍增LCA求调 qwq

我有预感，又是sb错误

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int LN = 17;

vector<int> g[N];
int n, m, dep[N], fa[20][N];

inline void AddEdge(int u, int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}

void dfs(int u, int last, int depth) {
	dep[u] = depth;
	fa[0][u] = last;
	for(int i = 0; i < g[u].size(); i++) {
		if(g[u][i] != last) {
			dfs(g[u][i], u, depth + 1);
		}
	}	
} 

int lca(int u, int v) {
	if(dep[u] > dep[v]) swap(u, v);
	int now = dep[v] - dep[u];
	for(int i = 0; i <= LN; i++) {
		if((now >> i) & 1) {
			v = fa[i][v];
		}
	}
	if(u == v) return u;
	for(int i = LN; i >= 0; i--) {
		if(fa[i][u] != fa[i][v]) {
			u = fa[i][u];
			v = fa[i][v];
		}
	}
	return fa[0][u];
} 

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		AddEdge(u, v);
	}
	dfs(1, 0, 0);
	for(int i = 1; i <= LN; i++) {
		for(int j = 1; j <= n; j++) {
			fa[i][j] = fa[i - 1][fa[i - 1][j]];
		}
	}
	while(m--) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		int p = lca(a, b), q = lca(c, d);
		if((dep[p] > dep[c] && dep[p] > dep[d]) || (dep[q] > dep[a] && dep[q] > dep[b])) {
			puts("N");
		}
		else if(dep[p] >= dep[q]) {
			if(lca(p, c) == p || lca(p, d) == p) puts("Y");
			else puts("N");
		}
		else {
			if(lca(q, a) == q || lca(q, b) == q) puts("Y");
			else puts("N");
		}
	}
	return 0;
}