oj | 【模板】LCA 点的距离 ## Description 求给定 \(m\) 组询问，每次询问 两个点之间在树上的距离 ## 输入 \(\boxed{\begin{align}&n&m\\&u_{1}&v_{1}\\&u_{2}&v_{2}\\&\vdots&n-1\text{ lines}\\&u_{n-1}&v_{n-1}\\&x_{1}&y_{1}\\&x_{2}&y_{2}\\&\vdots &m\text{ lines}\\&x_{n}&y_{n}\end{align}}\)
数据范围： - \(1\leq n\leq 10^6\) - \(1\leq m\leq 10^5\) - \(0\leq u,v,x,y\leq n-1\) - \(x\neq y\) ## 输出 输出 \(m\) 行，第 \(i\) 行包含一个整数，表示第 \(i\) 次询问的答案。
Sample Input
1 | 5 2 |
Sample Output
1 | 2 |
Notes
样例说明 
这种题一般是倍增算法和树链解刨分，tarjan 算法在求
[[../../ACM/图论/lca]] 用的不多。但是在求强连通分量用的最多 那么在求 LCA
时需要用到倍增。 1
dis(x,y)=dep[x]+dep[y]-2*dep[lca(x,y)];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
int n, m, r;
const int N = 1000010;
vector<int> e[N];
vector<pair<int, int>> query[N];
int fa[N], vis[N], ans[N],dis[N];
int find(int u)
{
if (u == fa[u])
return u;
return fa[u] = find(fa[u]);
}
void tarjan(int u)
{
vis[u] = 1;
for (auto v : e[u])
{
if (!vis[v])
{
dis[v] = dis[u] + 1;//
tarjan(v);
fa[v] = u;
}
}
for (auto q : query[u])
{
int v = q.first, i = q.second;
if (vis[v])
ans[i] = dis[u] + dis[v] - dis[find(v)] * 2;//
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
query[a].push_back({b, i});
query[b].push_back({a, i});
}
for (int i = 1; i <= n; i++)
fa[i] = i;
tarjan(0);
for (int i = 1; i <= m; i++)
cout << ans[i] << "\n";
}
题解
![[../../../../images/Z-attachment/Pasted image 20231224221840.png]]
董晓对于 loj10130 的三种方法代码
10130 . 「一本通 4.4 例 1」 点的距离 ### 倍增 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46//倍增算法
using namespace std;
const int N=100010,h=18;
int n,m,a,b;
vector<int> e[N];
int dep[N],fa[N][19],dis[N];
void dfs(int u,int father){
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1; i<=h; i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:e[u]){
if(v==father) continue;
dis[v]=dis[u]+1;
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=h; i>=0; i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return x;
for(int i=h; i>=0; i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main(){
scanf("%d",&n);
for(int i=1; i<n; i++){
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1,0);
scanf("%d",&m);
while(m--){
scanf("%d%d",&a,&b);
int d=dis[a]+dis[b]-dis[lca(a,b)]*2;
printf("%d\n",d);
}
return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52//树链剖分
using namespace std;
const int N=100010;
int n,m,a,b,c;
vector<int> e[N];
int dep[N],fa[N],son[N],sz[N],dis[N];
int top[N];
void dfs1(int u,int father){
fa[u]=father,dep[u]=dep[father]+1,sz[u]=1;
for(int v:e[u]){
if(v==father) continue;
dis[v]=dis[u]+1;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v])son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(int v:e[u]){
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int main(){
scanf("%d",&n);
for(int i=1; i<n; i++){
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
dfs1(1,0);
dfs2(1,1);
scanf("%d",&m);
while(m--){
scanf("%d%d",&a,&b);
int d=dis[a]+dis[b]-dis[lca(a,b)]*2;
printf("%d\n",d);
}
return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48//Tarjan 算法
using namespace std;
typedef pair<int,int> PII;
const int N=100010,M=N*2;
int n,m,a,b;
vector<int> e[N];
vector<PII> query[N];
int fa[N],vis[N],dis[N];
int ans[M];
int find(int u){
if(fa[u]==u) return u;
return fa[u]=find(fa[u]);
}
void tarjan(int u){
vis[u]=1;
for(int v:e[u]){
if(vis[v]) continue;
dis[v]=dis[u]+1;
tarjan(v);
fa[v]=u;
}
for(auto ed:query[u]){
int v=ed.first,i=ed.second;
if(vis[v])
ans[i]=dis[u]+dis[v]-dis[find(v)]*2;
}
}
int main(){
scanf("%d",&n);
for(int i=1; i<n; i++){
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
scanf("%d",&m);
for(int i=1; i<=m; i++){
scanf("%d%d",&a,&b);
query[a].push_back({b,i});
query[b].push_back({a,i});
}
for(int i=1;i<=n;i++) fa[i]=i;
tarjan(1);
for(int i=1; i<=m; i++)
printf("%d\n",ans[i]);
return 0;
}