【存档】树剖求lca
2025-07-23 01:17:04
发布于：湖南
24阅读
0回复
0点赞
切板子题进度 70%
呃呃呃我也不知道树剖英文名是啥
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int n, m, k;
class tree_spliter{
private:
vector <vector <int>> edges;
vector <int> dfn, dep, father, head, rank, son, siz;
int n;
void dfs(int cur, int fa){
father[cur] = fa;
siz[cur] = 1;
dep[cur] = dep[fa] + 1;
for(int i:edges[cur]){
if(i == fa) continue;
dfs(i, cur);
siz[cur] += siz[i];
if(siz[son[cur]] < siz[i]) son[cur] = i;
}
}
void dfs2(int cur, int top, int &curdfn){
head[cur] = top;
curdfn++;
dfn[cur] = curdfn;
rank[curdfn] = cur;
if(!son[cur]) return;
dfs2(son[cur], top, curdfn);
for(int i:edges[cur]){
if(i != son[cur] && i != father[cur]) dfs2(i, i, curdfn);
}
}
public:
tree_spliter(){}
void init(int n, vector <int> a, vector <vector <int>> v){
this -> n = n;
edges = v;
dfn.resize(n + 1);
father.resize(n + 1);
son.resize(n + 1);
siz.resize(n + 1);
head.resize(n + 1);
rank.resize(n + 1);
dep.resize(n + 1);
dfs(k, 0);
int curdfn = 0;
dfs2(k, k, curdfn);
}
int lca(int x, int y){
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]) y = father[head[y]];
else x = father[head[x]];
}
return (dep[x] < dep[y] ? x : y);
}
void test(){
cout << "father:\n";
for(int i = 1; i <= n; i++) cout << father[i] << ' ';
cout << "\nsiz:\n";
for(int i = 1; i <= n; i++) cout << siz[i] << ' ';
cout << "\ndep:\n";
for(int i = 1; i <= n; i++) cout << dep[i] << ' ';
cout << "\nson:\n";
for(int i = 1; i <= n; i++) cout << son[i] << ' ';
cout << "\nhead:\n";
for(int i = 1; i <= n; i++) cout << head[i] << ' ';
cout << "\ndfn:\n";
for(int i = 1; i <= n; i++) cout << dfn[i] << ' ';
cout << "\nrank:\n";
for(int i = 1; i <= n; i++) cout << rank[i] << ' ';
}
}t;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
vector <vector <int>> v(n + 1);
vector <int> a(n + 1);
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
v[x].push_back(y), v[y].push_back(x);
}
t.init(n, a, v);
//t.test();
while(m--){
int x, y;
cin >> x >> y;
cout << t.lca(x, y) << '\n';
}
return 0;
}
有帮助，赞一个