求助!!!
查看原帖
求助!!!
230394
wqqe223楼主2020/10/9 23:53

测试点2,9,10RE...

望大佬指出错误,不胜感激!!!

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
struct node
{
	int to;
};
vector<node>map[1000008];
int n, m, s;
int deep1, deep2;
int log2n;
int f[20][1000008] = { 0 };
int depth[1000008] = { 0 };
int loga[1000008] = { 0 };
int find(int p1, int p2);
int find(int p1, int p2)
{
	if (depth[p1] < depth[p2])
	{
		swap(p1, p2);
	}
	while (depth[p1] > depth[p2])
	{
		int up = (depth[p1] - depth[p2]);
		int i = loga[up]-1;
		p1 = f[i][p1];
	}
	if (p1 == p2)
		return p1;
	for (int i = loga[depth[p1]]-1; i >= 0; i--)
	{
		if (f[i][p1] != f[i][p2])
		{
			p1 = f[i][p1];
			p2 = f[i][p2];
		}
	}

	return f[0][p1];
}
void dfs(int fath, int now);
void dfs(int fath, int now)
{
	f[0][now] = fath;
	depth[now] = depth[fath] + 1;
	for (int i = 0; i < map[now].size(); i++)
	{
		if (map[now][i].to != fath)dfs(now, map[now][i].to);
	}
	return;
}
int main()
{

	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++)
	{
		loga[i] = loga[i - 1] + ((1 << loga[i - 1]) == i);
	}
	int log2n = loga[n] + 1;
	depth[s] = 0;
	int from, to;
	node e;
	for (int i = 1; i < n; i++)
	{
		cin >> from >> to;
		e.to = to;
		map[from].push_back(e);
		e.to = from;
		map[to].push_back(e);
	}
	depth[0] = -1;
	dfs(0,s);
	for (int i = 1; i <= log2n; i++)
		for (int j = 1; j <= n; j++)
			f[i][j] = f[i - 1][f[i - 1][j]];
	int point1, point2;
	for (int i = 1; i <= m; i++)
	{
		cin >> point1 >> point2;
		int ans = find(point1, point2);
		cout << ans << endl;
	}
	return 0;
}
2020/10/9 23:53
加载中...