全wa,已过样例
查看原帖
全wa,已过样例
1189340
aishiteru_mitsu_ha楼主2025/1/21 19:34
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
int n, m, fa[500005][25], deep[500005], ans;
vector<int>tree[500005];
inline void dfs1(int num, int pre, int dep);//搜深度
inline int dfs(int x, int y);//求LCA
inline int read()//快读
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	n = read(); m = read();
	fa[n][0] = n;
	for (int i = 1; i < n; i++) {
		fa[i][0] = i;
		int a, b;
		a = read(); b = read();
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs1(1, 0, 1);
	for (int j = 1; j <= log2(n); j++) {
		for (int i = 1; i <= n; i++) {
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
	for (int i = 1; i <= m; i++) {
		int x, y, z, lca1, lca2, lca3;
		x = read(); y = read(); z = read();
		lca1 = dfs(x, y);
		lca2 = dfs(x, z);
		lca3 = dfs(y, z);
		if (lca1 == lca2) ans = lca3;
		else if (lca2 == lca3) ans = lca1;
		else ans = lca2;
		//		cout<<"deep:"<<endl;
		//		for(int i=1;i<=n;i++) cout<<deep[i]<<" ";
		//		cout<<endl;
		cout << ans << " " << 0 - (deep[x] + deep[y] + deep[z] - deep[lca1] - deep[lca2] - deep[lca3]) << endl;
	}
	return 0;
}
void dfs1(int num, int pre, int dep) {
	//	cout<<"num="<<num<<" dep="<<dep<<endl;
	deep[num] = dep;
	for (auto i : tree[num]) {
		if (i != pre) {
			dfs1(i, num, dep + 1);
		}
	}
}
int dfs(int x, int y) {
	if (deep[x] < deep[y]) swap(x, y);
	int lg = log2(deep[x] - deep[y]);
	for (int i = lg; i >= 0; i--) {
		if (deep[fa[x][i]] < deep[y] || deep[fa[x][i]] == 0)
			continue;
		x = fa[x][i];
	}
	if (x == y) return x;
	lg = log2(deep[y]) + 1;
	for (int i = lg; i >= 0; i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	//	cout<<"fa[x][0]="<<fa[x][0]<<endl;
	return fa[x][0];
}
2025/1/21 19:34
加载中...