倍增LCA求助,样例过了但全WA
查看原帖
倍增LCA求助,样例过了但全WA
530349
天空即为极限楼主2022/1/16 11:43
#include<bits/stdc++.h>
using namespace std;
struct node{
	int to, next;
}k[500005];
int head[500005], number, fa[100005][31], dep[100005];
void add(int x, int y){
	k[++number].to = y;
	k[number].next = head[x];
	head[x] = number;
}
void dfs(int now, int f){
	dep[now] = dep[f] + 1;
	fa[now][0] = f;
	for(int i = 1; i <= 23; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for(int i = head[now]; i; i = k[i].next){
		if(k[i].to == f) continue;
		dfs(k[i].to, now);
	}
}
int LCA(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 21; i >= 0; i--)
		if(dep[fa[x][i]] >= dep[y]) 
			x = fa[x][i];
	if(x == y) return x;
	for(int i = 21; i >= 0; i--)
		if(fa[x][i] != fa[y][i]) 
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];			
}
int main(){
	int n, m, a, b, c, x;
	cin >> n >> m;
	for(int i = 1; i <= n - 1; i++){
		cin >> a >> b;
		add(a, b), add(b, a);
	}
//	dep[0] = -1;
	dfs(1, 0);
	for(int i = 1; i <= m; i++){
		cin >> a >> b >> c;
		x = max(LCA(a, b), max(LCA(b, c), LCA(a, c)));
		cout << x << " ";
		cout << dep[a] + dep[x] * 3 + dep[b] + dep[c] - 2 * dep[LCA(a, x)] - 2 * dep[LCA(b, x)] - 2 * dep[LCA(c, x)] << "\n";
	//	cout << "dep[a]:" << dep[a] << " dep[b]:" << dep[b] << " dep[x]:" << dep[c] << " dep[x]:" << dep[x] << "\n";
	}
	//cout << dep[1] << "\n";
} 
2022/1/16 11:43
加载中...