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;
}