• 注视一切的终结


    注视一切的终结

    题目大意

    给出一个 n n n 个点 m m m 条边的图,每条边有一个颜色 w i w_i wi 。保证这个图删除了所有重边后变成一棵树

    一条路径的权值就是相邻的两条边的 w i w_i wi 值不相同的个数

    Q Q Q 次询问,每次询问给出两个点 x , y x , y x,y ,求 x x x y y y 的所有简单路径的权值的最大值

    简单路径:路径上的所有顶点不重复。

    思路

    倍增、 d p dp dp

    显然,对于两个点之间的边,我们只用维护至多 3 3 3 种不同颜色的就可以了

    d p x , i , a , b dp_{x , i , a , b} dpx,i,a,b 表示一条 x x x 到距离它的 2 i 2^i 2i 距离的祖先的一条路径,靠近 x x x 的那一端的颜色是 a a a x x x 2 i 2 ^ i 2i 级祖先上面的那条边是 b b b 的路径的最大权值。

    那么
    f x , 0 , a , b = ( c o l a ≠ c o l b ) f_{x , 0 , a , b} = (col_a \neq col_b) fx,0,a,b=(cola=colb)
    转移是枚举 x , y = f a x , i − 1 , z = f a x , i x,y = fa_{x , i - 1} , z = fa_{x , i} x,y=fax,i1,z=fax,i ,颜色分别设为 a , b , c a , b , c a,b,c ,则转移为 f x , i , a , b = max ⁡ { f x , i − 1 , a , b + f y , i − 1 , b , c } f_{x , i , a , b} = \max\{f_{x , i - 1 , a , b} + f_{y , i - 1 , b , c}\} fx,i,a,b=max{fx,i1,a,b+fy,i1,b,c}

    对于每个询问 x , y x , y x,y

    设他们的 l c a lca lca 的儿子节点分别是 f x , f y fx , fy fx,fy ,分别求出 c x i , c y j cx_i , cy_j cxi,cyj 表示 f x , f y fx , fy fx,fy l c a lca lca 的所有不同颜色的边的最大权值。

    若其中一个点是 l c a lca lca ,那么答案就是另一个点的最大值,否则再枚举一遍 l c a lca lca 下两条边的颜色 a n s = max ⁡ { c x a + c y b + ( c o l a ≠ c o l b ) } ans = \max\{cx_a +cy_b + (col_a \neq col_b)\} ans=max{cxa+cyb+(cola=colb)}

    代码超级难调

    code

    #include 
    #define fu(x , y , z) for(int x = y ; x <= z ; x ++)
    #define fd(x , y , z) for(int x = y ; x >= z ; x --)
    using namespace std;
    const int N = 5e5 + 5 , M = 1e6 + 5;
    int ecnt , hd[N] , fa[N][21] , dep[N] , vis[N] , cnt[N] , col[N][4] , f[N][21][4][4] , n , m;
    struct E {
        int to , nt , w;
    } e[M << 1];
    void add (int x , int y , int z) { e[++ecnt].to = y , e[ecnt].w = z , e[ecnt].nt = hd[x] , hd[x] = ecnt; }
    int Lca (int x , int y) {
        if (dep[x] < dep[y]) swap (x , y);
        fd (i , 20 , 0) 
            if (dep[fa[x][i]] >= dep[y])
                x = fa[x][i];
        if (x == y) 
            return x;
        fd (i , 20 , 0) 
            if (fa[x][i] != fa[y][i])
                x = fa[x][i] , y = fa[y][i];
        return fa[x][0];
    }
    void dfs1 (int x) {
        vis[x] = 1;
        fu (i , 1 , 20) 
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        int y;
        for (int i = hd[x] ; i ; i = e[i].nt) {
            y = e[i].to;
            if (y == fa[x][0]) {
                if (cnt[x] == 3) continue;
                int flg = 0;
                fu (j , 1 , cnt[x]) 
                    if (col[x][j] == e[i].w) {
                        flg = 1;
                        break;
                    }
                if (flg) continue;
                col[x][++cnt[x]] = e[i].w;
            }
            if (vis[y]) continue;
            dep[y] = dep[x] + 1;
            fa[y][0] = x;
            dfs1 (y);
        }
    }
    void dfs2 (int x) {
        vis[x] = 1;
        int y;
        if (x != 1) {
            y = fa[x][0];
            fu (j , 1 , cnt[x]) 
                fu (k , 1 , cnt[fa[x][0]])
                    f[x][0][j][k] = (col[x][j] != col[fa[x][0]][k]); 
        }
        int z;
        for(int i=1;(1<<i)<=dep[x];i++) {
            y = fa[x][i - 1] , z = fa[x][i];
            fu (a , 1 , cnt[x]) {
                fu (b , 1 , cnt[y]) {
                    fu (c , 1 , cnt[z]) {
                        f[x][i][a][c] = max (f[x][i][a][c] , f[x][i - 1][a][b] + f[y][i - 1][b][c]);
                    }
                }
            }
        }
        for (int i = hd[x] ; i ; i = e[i].nt) {
            y = e[i].to;
            if (vis[y]) continue;
            dfs2 (y);
        }
    }
    int jump (int x , int d , int c[]) {
        int cc[5] , y;
        fd (i , 20 , 0) {
            if (dep[fa[x][i]] > d) {
                y = fa[x][i];
                memset (cc , 0 , sizeof (cc));
                fu (a , 1 , cnt[x])
                    fu (b , 1 , cnt[y])
                        cc[b] = max (cc[b] , c[a] + f[x][i][a][b]);
                x = fa[x][i];
                memcpy (c , cc , sizeof (cc));
            }
        }
        return x;
    }
    int main () { 
        // freopen ("a.in" , "r" , stdin);
        // freopen ("c.out" , "w" , stdout);
        int u , v , w;
        scanf ("%d%d" , &n , &m);
        fu (i , 1 , m) {
            scanf ("%d%d%d" , &u , &v , &w);
            add (u , v , w) , add (v , u , w);
        }
        dep[1] = 1;
        dfs1 (1);
        fu (i , 1 , n) vis[i] = 0;
        dfs2 (1);
        int T , x , y , lca , fx , fy , cx[5] , cy[5] , ans;
        scanf ("%d" , &T);
        int ans1 =  0;
        while (T --) {
            memset (cx , 0 , sizeof (cx)) , memset (cy , 0 , sizeof (cy));
            fx = fy = 0;
            scanf ("%d%d" , &x , &y);
            lca = Lca (x , y);
            if (x != lca) fx = jump (x , dep[lca] , cx);
            if (y != lca) fy = jump (y , dep[lca] , cy);
            ans = 0;
            if (x == lca)
                fu (i , 1 , cnt[fy]) 
                    ans = max (ans , cy[i]);
            else if (y == lca) 
                fu (i , 1 , cnt[fx])
                    ans = max (ans , cx[i]);
            else {
                fu (i , 1 , cnt[fx]) {
                    fu (j , 1 , cnt[fy]) {
                        ans = max (ans , cx[i] + cy[j] + (col[fx][i] != col[fy][j]));
                    }
                }
            } 
            printf ("%d\n" , ans);
        }
        return 0;
    }
    
    • 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
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
  • 相关阅读:
    [车联网安全自学篇] 八. ATTACK安全之车机(Android)设备中监控命令执行的一些想法【概念篇】
    centos——开启/关闭oracle
    微服务项目:尚融宝(26)(后端搭建:Nuxt.js入门)
    主动成为行业发展的一份子,正在成为一种潮流和趋势
    Python魔法方法
    CVE-2021-4034 polkit提权漏洞复现
    AI应用新时代的起点,亚马逊云科技加速大模型应用
    JAVA 开发相关软件介绍以及安装使用教程(初学者一定要收藏)
    设计模式——单例模式8种实现
    2022-8-20 B树和B+树
  • 原文地址:https://blog.csdn.net/fzyyyyyyyy/article/details/133916287