LCA专项练习

LCA专项练习

前提提要

由于A,B太水了,就不放了。

前几题先试试用trajan能不能全杀,之后再看在线算法。


易错点统计

  1. 如果两个点相同,那么他们的祖先节点居然会变成0。。可能是我的模板写法有点问题。可以在判断vis[u]=2的时候加上如果u=now也是找到了公共祖先。
  2. i=fa[j]; 应该是fa[j] = i;
  3. 如果要加入假设边的话,G[maxn<<2]得开4倍大小,不然会已知TLE。。
  4. 有时候两种不同的写法不能混淆。
  5. 两个点相同又错了。ST表写法的时候也得特判的时候还是要考虑一下,因为有的题目不是单纯的距离之差。

C - Distance Queries

题意

一棵树,求两点之间最短距离。

题解

裸LCA+dfs求距离

AC代码

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
99
100
101
102
103
104
105
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4+100;
struct Query{
int to,id;
Query(){}
Query(int a,int b){
to = a;id = b;
}
};
vector<Query> query[maxn];
struct node{
int to,next,val;
}G[maxn<<2];
int n,m,cnt;
int head[maxn],vis[maxn],fa[maxn],ans[maxn],dis[maxn];
void add(int u,int v,int val){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].val = val;
head[u] = cnt++;
}
void init(){
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
memset(dis,0,sizeof(dis));
rep(i,1,n+1) query[i].clear();
rep(i,1,n+1) fa[i] = i;
cnt = 0;
}
void dfs1(int u,int f){
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==f) continue;
dis[v] = dis[u] + G[i].val;
dfs1(v,u);
}
}
int find(int x){
if(x!=fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void dfs(int now){
vis[now] = 1;
for(int i=head[now];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]) continue;
dfs(v);
fa[v] = now;
}
for(int i = 0;i<query[now].size();i++){
Query node = query[now][i];
int u = node.to; int id = node.id;
if(vis[u]==2){
ans[id] = find(u);
}
}
vis[now] = 2;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)){
init();
vector<pair<int,int> > ask;
rep(i,0,m){
int u,v,val;scanf("%d%d%d",&u,&v,&val);
char s[10]; scanf("%s",s);
add(u,v,val); add(v,u,val);
}
dfs1(1,-1);
int t;scanf("%d",&t);
rep(i,0,t){
int u,v;
scanf("%d%d",&u,&v);
query[u].push_back(Query(v,i));
query[v].push_back(Query(u,i));
ask.push_back(make_pair(u,v));
}
dfs(1);
rep(i,0,t){
int x = ask[i].fi,y = ask[i].se;
if(x==y){
puts("0");
continue;
}
printf("%d\n",dis[x]-dis[ans[i]]+dis[y]-dis[ans[i]]);
}
}
return 0;
}

修订版。在LCA里面特判。

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
99
100
101
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4+100;
struct Query{
int to,id;
Query(){}
Query(int a,int b){
to = a;id = b;
}
};
vector<Query> query[maxn];
struct node{
int to,next,val;
}G[maxn<<2];
int n,m,cnt;
int head[maxn],vis[maxn],fa[maxn],ans[maxn],dis[maxn];
void add(int u,int v,int val){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].val = val;
head[u] = cnt++;
}
void init(){
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
memset(dis,0,sizeof(dis));
rep(i,1,n+1) query[i].clear();
rep(i,1,n+1) fa[i] = i;
cnt = 0;
}
void dfs1(int u,int f){
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==f) continue;
dis[v] = dis[u] + G[i].val;
dfs1(v,u);
}
}
int find(int x){
if(x!=fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void dfs(int now){
vis[now] = 1;
for(int i=head[now];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]) continue;
dfs(v);
fa[v] = now;
}
for(int i = 0;i<query[now].size();i++){
Query node = query[now][i];
int u = node.to; int id = node.id;
if(vis[u]==2 || u==now){
ans[id] = find(u);
}
}
vis[now] = 2;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)){
init();
vector<pair<int,int> > ask;
rep(i,0,m){
int u,v,val;scanf("%d%d%d",&u,&v,&val);
char s[10]; scanf("%s",s);
add(u,v,val); add(v,u,val);
}
dfs1(1,-1);
int t;scanf("%d",&t);
rep(i,0,t){
int u,v;
scanf("%d%d",&u,&v);
query[u].push_back(Query(v,i));
query[v].push_back(Query(u,i));
ask.push_back(make_pair(u,v));
}
dfs(1);
rep(i,0,t){
int x = ask[i].fi,y = ask[i].se;
printf("%d\n",dis[x]-dis[ans[i]]+dis[y]-dis[ans[i]]);
}
}
return 0;
}

D - Connections between cities

题意

分成未知数目颗树,问其中两点是否有路径,路径的最短长度是多少。

题解

LCA+假点。

但是这道题的内存有点卡,导致不能用vector存询问,还是用两个链式前向星还行。

AC代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m,c,cnt,tot;
const int maxn = 1e4+1000;
struct node{
int next,to,val;
}G[maxn<<2];
int head[maxn],fa[maxn],vis[maxn],ans[maxn*200],dis[maxn],headq[maxn];
void add(int u,int v,int val){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].val = val;
head[u] = cnt++;
}
struct Query{
int next,to;
}query[maxn*200];
int find(int x){
if(x!=fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void addq(int u,int v){
query[tot].to = v;
query[tot].next = headq[u];
headq[u] = tot++;
}
void dfs(int now){
vis[now] = 1;
for(int i=headq[now];~i;i=query[i].next){
int v = query[i].to;
if(vis[v]){
if(v==now){
ans[i/2] = 0;
continue;
}
if(find(v)==0) ans[i/2] = -1;
else ans[i/2] = dis[now]+dis[v]-2*dis[find(v)];
}
}
for(int i=head[now];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]) continue;
dis[v] = dis[now] + G[i].val;
dfs(v);
fa[v] = now;
}
}
void init(){
memset(head,-1,sizeof(int)*(n+2));
memset(headq,-1,sizeof(int)*(n+2));
memset(vis,0,sizeof(int)*(n+1));
rep(i,1,n+1) fa[i] = i;
cnt = 0;
tot = 0;
}
void Union(int a,int b){
int i = find(a), j = find(b);
if(i==j) return;
fa[i] = j;
}
template <typename T>
inline bool read (T &ret) {
char c;
int sgn;
if (c = getchar(), c == EOF) return 0; //EOF
while (c != '-' && (c < '0' || c > '9') ) {
if((c = getchar()) == EOF) return 0;
}
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
while(~scanf("%d%d%d",&n,&m,&c)){
init();
rep(i,0,m){
int u,v,val;read(u);read(v);read(val);
add(u,v,val); add(v,u,val);
Union(u,v);
}
rep(i,1,n+1){
if(fa[i] == i) fa[i] = 0;
add(0,i,0); add(i,0,0);
}
rep(i,0,c){
int u,v; read(u); read(v);
addq(u,v); addq(v,u);
}
rep(i,1,n+1) fa[i] = i;
dfs(0);
rep(i,0,c){
if(ans[i]==-1){
puts("Not connected");
continue;
}
printf("%d\n",ans[i]);
}
}

return 0;
}

F - Tree

题意

对于一棵树有如下两种操作

  • 将$v$,$v$两个点之间所有的点包括这两个点的权值全部加$val$
  • 将$v$,$v$两个点之间所有的边的权值全部加$val$

题解

lca+标记递推

我们定义$add[x][0]$为在$x$点上往后递推的点值,那么对于两个$u,v$来说我们要让这条链上的所有点都加$val$。

1
2
3
4
add[u][0] += val;
add[v][0] += val;
add[x][0] -= val;
des[x] -= val;

其中$x$是他们的LCA,而且为了使得到了他们的LCA不继续增加这个值,我们定义一个数组$des[]$,递推的时候就加上这个数组在递推,就可以使得在LCA的时候不递推到LCA的祖先节点了。

树链剖分题解

树链剖分可以处理点权和边权,不过这是我第一次看到一起处理的。

trick:

把点用数组存起来,到边的时候就用孩子节点来表示孩子节点到父亲节点的边。

ac代码

G - One and One Story

H - CD操作

题意

一个加一点背景的LCA,往父节点走要+1,从祖先节点到任意子节点也只需要加1。

题解

LCA,我用了ST表+RMQ,跑的飞快。

AC代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int cnt,n,m;
int head[maxn];
int fa[maxn];
struct node{
int next,to;
}G[maxn<<1];
void addedge(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
struct ST{
int tot;
int first[maxn<<1],R[maxn<<1],order[maxn<<1],dp[maxn<<1][20],dis[maxn];
void init(int root){
tot = 0;
dfs(root,0,-1);
ST_init(tot);
}
void ST_init(int n){
rep(i,1,n+1) dp[i][0] = i;
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
int a = dp[i][j-1],b = dp[i+(1<<(j-1))][j-1];
dp[i][j] = R[a]<R[b]?a:b;
}
}
}
int LCA(int u,int v){
int x = first[u],y = first[v];
if(x>y) swap(x,y);
int res = RMQ(x,y);
return order[res];
}
int RMQ(int l,int r){
int k = 0;
while((1<<(k+1))<=r-l+1) k++;
int a = dp[l][k],b = dp[r-(1<<k)+1][k];
return R[a]<R[b]?a:b;
}
void dfs(int u,int deep,int f){
R[++tot] = deep;
dis[u] = deep;
order[tot] = u;
first[u] = tot;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==f) continue;
dfs(v,deep+1,u);
order[++tot] = u;
R[tot] = deep;
}
}
}st;
int find(int x){
return x==fa[x]?x:fa[x] = find(fa[x]);
}
int ind[maxn];
char s[60];
void init(){
cnt = 0;
memset(head,-1,sizeof(head));
memset(ind,0,sizeof(ind));
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
map<string,int> mp;
int tot = 0;
rep(i,0,n-1){
int u,v;
scanf("%s",s);
if(mp[s]==0) mp[s] = ++tot,u = tot;
else u = mp[s];
scanf("%s",s);
if(mp[s]==0) mp[s] = ++tot,v = tot;
else v = mp[s];
addedge(v,u); ind[u]++;
}
int root = 0;
rep(i,1,n+1) if(ind[i]==0){
root = i;
break;
}
st.init(root);
rep(i,0,m){
int u,v,ans;
scanf("%s",s); u = mp[s];
scanf("%s",s); v = mp[s];
int rt = st.LCA(u,v);
int x = st.dis[u] - st.dis[rt];
int y = st.dis[v] - st.dis[rt];
if(rt==u) ans = 1;
else if(rt == v) ans = x;
else ans = x+1;
if(u==v) ans = 0;
printf("%d\n",ans);
}
}
return 0;
}