@[wangziwenhk](/user/727556) 虽然但是，你这个树剖是不是写的有点抽象啊
by Hoks @ 2024-03-27 17:02:46
@[wangziwenhk](/user/727556) 你疑似对子树大小 ```size``` 的定义有误解，子树大小应为子树点数，而不是儿子个数，且求lca时应比较两者 ```top``` 的深度。
by __Chx__ @ 2024-03-27 17:19:27
并且建议用 ```vector``` 存边，数组记录每个点的信息，使用 ```map``` 多一个 $\log$ 的复杂度。
by __Chx__ @ 2024-03-27 17:23:54
@[__Chx__](/user/753355) 感谢，已关
by wangziwenhk @ 2024-03-28 14:11:06
@[__Chx__](/user/753355) 但是 Sub1 #2还是T了
```c++
#include <bits/stdc++.h>
using namespace std;
struct Node{
vector<int>child;
int size,father,deep;
int bestSon,top;
};
array<vector<int>,500050>graph;
array<Node,500050>tree;
int n,m,s;
int build(int x,int father,int deep){
tree[x].father = father;
tree[x].deep = deep;
int k=-1,v=-1,t;
for(auto i:graph[x]){
if(i == father)continue;
t = build(i,x,deep+1);
if(t>v){
v = t;
k = i;
}
tree[x].child.push_back(i);
}
tree[x].bestSon = k;
tree[x].size = graph[x].size()+1;
return tree[x].size;
}
void link(int x,int top){
tree[x].top = top;
if(tree[x].bestSon==-1)return;
for(auto i:tree[x].child){
if(tree[x].bestSon==i)link(i,top);
else link(i,i);
}
}
int lca(int x,int y){
while(tree[x].top != tree[y].top){
int tx = tree[x].top;
int ty = tree[y].top;
if(tree[tx].deep>tree[ty].deep){
if(tree[x].top == x)x = tree[x].father;
else x = tree[x].top;
}
else{
if(tree[y].top == y)y = tree[y].father;
else y = tree[y].top;
}
}
return tree[x].deep > tree[y].deep ? y : x;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x==y)continue;
graph[x].push_back(y);
graph[y].push_back(x);
}
build(s,s,1);
link(s,s);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n", lca(x,y));
}
}
```
by wangziwenhk @ 2024-03-28 14:32:08
@[wangziwenhk](/user/727556) ```size```的概念应该为子树的点数，此处 ```graph[x].size()+1```意为点 $x$ 的边数+1，应改为：
```
int build(int x,int father,int deep){
tree[x].father = father;
tree[x].deep = deep;
tree[x].size = 1;
int k=-1,v=-1,t;
for(auto i:graph[x]){
if(i == father)continue;
t = build(i,x,deep+1);
if(t>v){
v = t;
k = i;
}
tree[x].size += t;
tree[x].child.push_back(i);
}
tree[x].bestSon = k;
return tree[x].size;
}
```
by __Chx__ @ 2024-03-28 14:40:23
建议模板题可适当学习一些题解的优秀写法
by __Chx__ @ 2024-03-28 14:42:29
@[__Chx__](/user/753355) 懂了，谢谢
by wangziwenhk @ 2024-03-28 14:43:20