测试点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;
}