【LCA】Tarjan

今天的题目是LCA最近公共祖先
LCA
两道题都是模板题,第一道题没有用 $Tarjan$

Nearest Common Ancestors

题意

给一棵树,给两个点编号,求他们的最近公共祖先

思路:
直接让他们给👴往上爪巴,然后打标记,第一个碰到的标记就是答案。

尽然过了

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
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int maxn = 1e4 + 10;

int p[maxn];
int vis[maxn];

int main(){
int T;scanf("%d",&T);
while(T--){
memset(p,0,sizeof p);
memset(vis,0,sizeof vis);
int n;scanf("%d",&n);

int u,v;
for(int i = 1;i < n;i++){
scanf("%d%d",&u,&v);
p[v] = u;
}
scanf("%d%d",&u,&v);
while(u != p[u]){
vis[u] = 1;
u = p[u];
}

while(!vis[v]){
v = p[v];
}

printf("%d\n",v);
}
}

D.How far away ?

题意

给一棵树,带有边权,给两个点,求最短距离

思路
设 $dis[i]$ 为节点 $i$ 到根节点的距离,则 $ans = dis[u] + dis[v] - 2 * dis[Lca(u,v)]$

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;

const int maxn = 8e4 + 10;

int vis[maxn];
int par[maxn];
int ans[maxn];
int dis[maxn];
int n,m;

struct E{
int to,w,next;
}Edges[maxn];
int head[maxn];

int cnt;

vector<pair<int,int> >L[maxn];


void addEdge(int from,int to,int w){
Edges[cnt] = E{to,w,head[from]};
head[from] = cnt++;
}

int get_par(int a){
if(par[a] != a){
par[a] = get_par(par[a]);
}
return par[a];
}

void merge(int u,int v){
par[get_par(u)] = get_par(v);
}

void init(int n){
for(int i = 0;i <= n;i++){
par[i] = i;
dis[i] = 0;
vis[i] = 0;
head[i] = -1;
L[i].clear();
ans[i] = 0;
}
}

void Tarjan(int u,int d){

vis[u] = 1;
dis[u] = d;

for(int i = head[u];i != -1;i = Edges[i].next){
int to = Edges[i].to;
if(vis[to])continue;
Tarjan(to,dis[u] + Edges[i].w);
merge(to,u);
}

for(int i = 0;i < L[u].size();i++){
int to = L[u][i].first;
int k = L[u][i].second;

if(vis[to]){
ans[k] = dis[to] + dis[u] - 2 * dis[get_par(to)];
}
}

}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init(n);

for(int i = 1;i < n;i++){
int from,to,w;
scanf("%d%d%d",&from,&to,&w);
addEdge(from,to,w);
addEdge(to,from,w);
}

for(int i = 0;i < m;i++){
int x,y;
scanf("%d%d",&x,&y);
L[x].push_back(pair<int,int>{y,i});
L[y].push_back(pair<int,int>{x,i});
}

Tarjan(1,0);

for(int i = 0;i < m;i++){
printf("%d\n",ans[i]);
}

}
}