20220108-路径重建

发表于 更新于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

路径重建

本篇文章主要收集了和路径重建相关的算法题，希望会对目前所研究的问题带来些启发。

1. 阻断

  • 题意：https://www.luogu.com.cn/problem/P4374

  • 题解：https://www.luogu.com.cn/problem/solution/P4374

  • 思路：【树剖+线段树】

    image.png

    • 发现每次加入一条额外边，假设两端点分别为x和y，则这条边会和原来树上x和y之间的链构成一个环。这个环上的任何一条树边被砍断，断开的两个连通块一定可以通过我们刚加的这条额外边保持连通。同时，如果一条树边不在这个环上，那么如果砍断这条边，这条额外的边也无法使树保持连通。
    • 因此我们进行边转点。在点的时间戳上建立线段树，线段树每片叶子维护“删掉这个点所代表的边后，使树连通需要的最短边的边权”。区间信息不用合并，因为是单点查询。
    • 我们每次读入端点为x和y，权值为k的额外边，常规树剖写法，在树上以x和y为端点的链上进行min(k, w[i])；查询的时候先得到这条边对应的点，然后单点查询即可；
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
#include<bits/stdc++.h>
using namespace std;
int ans[50010];
int n, m;
int par[50010][17];
int dep[50010], po[50010], to[50010];
vector<pair<int, int>> G[50010];
pair<int, pair<int, int>> roads[50010];

int getto(int x){
    if(to[x] == x)  return x;
    return to[x] = getto(to[x]);
}

void dfs(int x, int p){
    for(int i = 0; i < G[x].size(); i++){
        int y = G[x][i].first, id = G[x][i].second;
        if(y == p)  continue;
        po[id] = y;
        par[y][0] = x;
        dep[y] = dep[x] + 1;
        dfs(y, x);
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 16; i >= 0; i--){
        if(dep[par[x][i]] >= dep[y]){
            x = par[x][i];
        }
    }
    if(x == y)  return x;
    for(int i = 16; i >= 0; i--){
        if(par[x][i] != par[y][i]){
            x = par[x][i], y = par[y][i];
        }
    }
    return par[x][0];
}


int main(){
    cin>>n>>m;
    for(int i = 1; i < n; i++){
        int x, y;   cin>>x>>y;
        G[x].push_back(make_pair(y, i));
        G[y].push_back(make_pair(x, i));
    }
    
    for(int i = 1; i <= m; i++){
        int x, y, z;    cin>>x>>y>>z;
        roads[i] = make_pair(z, make_pair(x, y));
    }
    
    dep[0] = -1;
    dfs(1, 0);
    for(int i = 1; i <= 16; i++){
        for(int j = 1; j <= n; j++){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
    
    for(int i = 1; i <= n; i++) to[i] = i;
    for(int i = 1; i <= n; i++) ans[i] = -1;
    sort(roads+1, roads+m+1);
    for(int i = 1; i <= m; i++){
        int v = roads[i].first;
        int x = roads[i].second.first, y = roads[i].second.second;
        int xy = lca(x, y);
        for(x = getto(x); dep[x] > dep[xy]; x = getto(par[x][0])){
            ans[x] = v;
            to[x] = par[x][0];
        }
        
        for(y = getto(y); dep[y] > dep[xy]; y = getto(par[y][0])){
            ans[y] = v;
            to[y] = par[y][0];
        }
    }
    for(int i = 1; i < n; i++)  cout<<ans[po[i]]<<endl;
    return 0;
}