# 14127: 【原4127】lca

### 题目描述

author: Lmxyy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4127

## Description

dhh最近学了lca，可高兴了。他现在可以在\(O(logN)\)的时间里求两个点的lca了。

dhh想了想，觉得好像真的有点小解。但他嘴上却说：”哪里解了？“

xyy说：”那我来考考你，给你一棵\(N\)个点的无根树，每次询问一组\(u,v,w\)，问以\(w\)为根的树，\(u\)和\(v\)这两个点的lca是什么？“

dhh一时脸红了。。。他答不上来，所以向你求助。

## Sample Input

``````6
2 4
1 4
3 2
1 6
5 4
6
1 5 1
6 3 5
6 3 6
6 4 5
4 2 4
5 1 5
``````

## Sample Output

``````1
4
6
4
4
5
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

class edge {
public:
int to = 0;
edge* next = nullptr;
};

class tree_node {
public:
int parent = 0;
int depth = 0;
int parent_list[24] = { 0 };
edge* head = nullptr, * rear = nullptr;
};

tree_node tree_data[100009];
int root_pos = 0;

void dfs(int pos) {
if (pos == root_pos) {
tree_data[pos].depth = 0;
}
else {
tree_data[pos].depth = tree_data[tree_data[pos].parent].depth + 1;
int k = (int)(log(tree_data[pos].depth) / log(2));
tree_data[pos].parent_list[0] = tree_data[pos].parent;
for (int i = 1; i <= k; ++i) {
tree_data[pos].parent_list[i] = tree_data[tree_data[pos].parent_list[i - 1]].parent_list[i - 1];
}
}
for (auto p = tree_data[pos].head->next; p; p = p->next) {
if (p->to != tree_data[pos].parent) {
tree_data[p->to].parent = pos;
dfs(p->to);
}
}
}

int LCA(int pos1, int pos2) {
while (tree_data[pos1].depth < tree_data[pos2].depth) {
int k = int(log(tree_data[pos2].depth - tree_data[pos1].depth) / log(2));
pos2 = tree_data[pos2].parent_list[k];
}
while (tree_data[pos2].depth < tree_data[pos1].depth) {
int k = int(log(tree_data[pos1].depth - tree_data[pos2].depth) / log(2));
pos1 = tree_data[pos1].parent_list[k];
}
while (pos1 != pos2) {
int k = int(log(tree_data[pos1].depth) / log(2));
for (int i = k; i >= 0; --i) {
if (i == 0 || tree_data[pos1].parent_list[i] != tree_data[pos2].parent_list[i]) {
pos1 = tree_data[pos1].parent_list[i];
pos2 = tree_data[pos2].parent_list[i];
}
}
}
return pos1;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

for (int i = 1; i <= n; ++i) {
tree_data[i].rear = tree_data[i].head = new edge;
}

for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;

tree_data[u].rear->next = new edge;
tree_data[u].rear = tree_data[u].rear->next;
tree_data[u].rear->to = v;

tree_data[v].rear->next = new edge;
tree_data[v].rear = tree_data[v].rear->next;
tree_data[v].rear->to = u;
}

root_pos = 1;
dfs(1);

int q;
cin >> q;

for (; q > 0; --q) {
int u, v, w;
cin >> u >> v >> w;
int lca1 = LCA(u, v), lca2 = LCA(u, w), lca3 = LCA(v, w);
if (tree_data[lca1].depth < tree_data[lca2].depth) {
if (tree_data[lca3].depth > tree_data[lca2].depth) {
cout << lca3 << "\n";
}
else {
cout << lca2 << "\n";
}
}
else {
if (tree_data[lca3].depth > tree_data[lca1].depth) {
cout << lca3 << "\n";
}
else {
cout << lca1 << "\n";
}
}
}

return 0;
}
``````

## zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4127.md
*/
#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, q, ans[500005] = {0}, tans[1500005];
int at[100005] = {0}, nxt[200005], to[200005], cnt = 0;
int at2[3000005] = {0}, nxt2[3000005], to2[3000005], cnt2 = 0;
int par[100005], dep[100005];
bool vis[100005] = {0}, typ[500005] = {0};
int Find(int x){
return (par[x] == x ? x: (par[x] = Find(par[x])));
}
void Union(int xxxx, int yyyy){
int u = Find(xxxx), v = Find(yyyy);
if (u == v) return ;
par[u] = v;
}
void init(){
for (int i = 1; i < n; ++i){
to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
}
for (int i = 1; i <= q; ++i){
to2[++cnt2] = v, nxt2[cnt2] = at2[u], at2[u] = cnt2;    // u v
to2[++cnt2] = u, nxt2[cnt2] = at2[v], at2[v] = cnt2;    // v u
to2[++cnt2] = u, nxt2[cnt2] = at2[w], at2[w] = cnt2;    // w u
to2[++cnt2] = w, nxt2[cnt2] = at2[u], at2[u] = cnt2;    // u w
to2[++cnt2] = w, nxt2[cnt2] = at2[v], at2[v] = cnt2;    // v w
to2[++cnt2] = v, nxt2[cnt2] = at2[w], at2[w] = cnt2;    // w v
}
}
void dfs(int cur, int fa){
par[cur] = cur;
for (int i = at[cur]; i; i = nxt[i]){
int v = to[i];
if (v == fa) continue;
dep[v] = dep[cur] + 1, dfs(v, cur), Union(v, cur);
}
vis[cur] = true;
for (int i = at2[cur]; i; i = nxt2[i]){
int v = to2[i];
if (i % 6 == 0){
// as a root, determine the type
int u = to2[i - 3], ccnt = 0;
if (Find(u) == cur) ++ccnt;
if (Find(v) == cur) ++ccnt;
if (ccnt == 2) typ[i / 6] = false;  // both in w
else if (ccnt == 1) ans[i / 6] = cur;
else typ[i / 6] = true;

if (vis[v])
tans[i / 2] = Find(v);
}else {
if (!vis[v]) continue;
int iid = (i / 6), idx = i % 6;
if (idx <= 2)
tans[iid * 3 + 1] = Find(v);
else if (idx <= 4)
tans[iid * 3 + 2] = Find(v);
else
tans[iid * 3 + 3] = Find(v);
}
}
}
void solve(){
dep[1] = 0;
dfs(1, 0);
for (int i = 1; i <= q; ++i){
ans[i] = tans[i * 3 - 2];
if (dep[ans[i]] < dep[tans[i * 3 - 1]])
ans[i] = tans[i * 3 - 1];
if (dep[ans[i]] < dep[tans[i * 3]])
ans[i] = tans[i * 3];
}
for (int i = 1; i <= q; ++i)
printf("%d\n", ans[i]);
}
int main(){
init();
solve();
return 0;
}
``````