HDU 5266 pog loves szh III (LCA)

时间:2023-01-06 21:00:50

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5266

题目就是让你求LCA,模版题。注意dfs会栈溢出,所以要扩栈,或者用bfs写。

 #pragma comment(linker, "/STACK:102400000,102400000") //扩栈
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 3e5 + ;
struct data {
int next , to;
}edge[MAXN << ];
int par[MAXN][] , head[MAXN] , cnt , dep[MAXN]; inline void add(int u , int v) {
edge[cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt++;
} void dfs(int u , int d , int p) {
dep[u] = d;
par[u][] = p;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dfs(v , d + , u);
}
} void init(int n) {
for(int k = ; k < ; ++k) {
for(int i = ; i <= n ; ++i) {
if(par[i][k] <= )
par[i][k + ] = par[i][k];
else
par[i][k + ] = par[par[i][k]][k];
}
}
} int lca(int u , int v) {
if(dep[u] < dep[v])
swap(u , v);
for(int k = ; k < ; ++k) {
if(((dep[u] - dep[v]) >> k) & ) {
u = par[u][k];
}
}
if(u == v)
return u;
for(int k = ; k >= ; --k) {
if(par[u][k] != par[v][k]) {
u = par[u][k];
v = par[v][k];
}
}
return par[u][];
} int main()
{
int n , q , u , v;
while(~scanf("%d" , &n)) {
cnt = ;
memset(head , - , sizeof(head));
for(int i = ; i < n ; ++i) {
scanf("%d %d" , &u , &v);
add(u , v);
add(v , u);
}
dfs( , , -);
init(n);
scanf("%d" , &q);
for(int i = ; i < q; ++i) {
scanf("%d %d" , &u , &v);
printf("%d\n" , lca(u , v));
}
}
}