分类: 专项练习 - CheaSim Blog
发表更新专项练习14 分钟读完 (大约2063个字)

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
115
#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;
}
关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×