• 动态树的第2大值

    一 问题描述

    一棵有 N 个节点的树，节点编号为 1..N。每个节点都有一个权值。有 4 种类型的操作：

    ① 1 x y a b ，从树中删除一条边 x -y ，然后添加一条新边 a -b ；确保在添加新边后它仍然构成树。

    ② 2 a b w ，将节点 a 和 b 路径上所有节点（包括a 和b）的权值都修改为 w。

    ③ 3 a b d ，将节点 a 和 b（包括 a 和 b ）路径上所有节点的权值都增加 d。 

    ④ 4 a b ，查询节点 a 和 b （包括 a 和 b ）路径上的第 2 大权值，以及该权值在路径上出现的次数。

    注意：这里是严格的第 2 大权值。{3, 5, 2, 5, 3} 的严格第 2 大权值是 3。

    二 输入和输出

    1 输入

    第 1 行包含一个整数 T（T ≤ 3），表示测试用例数。每个测试用例的第 1 行都包含两个整数 N 和 M（ N、M ≤10^5 ），表示节点数和操作数；第2行包含 N 个整数，表示节点的权值；接下来的 N-1 行，每行都包含两个整数 a 和 b ，表示在节点 a 和 b 之间有一条边；最后 M 行描述操作。其中，1≤x , y , a , b ≤N ，|w |≤10^4 ，|d|≤10^4 。

    2 输出

    对每个测试用例，都先单行输出“Case #x :”（x 表示测试用例编号）；对每个查询操作都输出两个值，即第 2 大权值及其出现的次数。若路径上所有节点的权值都相同，则输出“ALL SAME”。

    三 输入和输出样例

    1 输入样例

    2

    3 2

    1 1 2

    1 2

    1 3

    4 1 2

    4 2 3

    7 7

    5 3 2 1 7 3 6

    1 2

    1 3

    3 4

    3 5

    4 6

    4 7

    4 2 6

    3 4 5 -1

    4 5 7

    1 3 4 2 4

    4 3 6

    2 3 6 5

    4 3 6

    2 输出样例

    Case #1:

    ALL SAME

    1 2

    Case #2:

    3 2

    1 1

    3 2

    ALL SAME

    四 图解

    根据输入样例 2，构建的树形结构如下图所示。

    它对应的 7 种操作如下。

    （1）4 2 6：查询 2-6 路径上的第 2 大权值和该权值的重复次数。2-6 路径上的第 2 大权值为 3，该权值的重复次数为 2，所以输出 3 2。

    （2）3 4 5 -1：将 4-5 路径上所有节点的权值都减 1。

    （3）4 5 7：查询 5-7 路径上的第 2 大权值和该权值的重复次数，路径 5-7 上的第 2 大权值为 1，该权值的重复次数为 1，输出 1 1。

    （4）1 3 4 2 4：删除 3-4 的边，添加 2-4 的边。

    （5）4 3 6：查询 3-6 路径上的第 2 大权值和该权值的重复次数，路径 3-6 上的第 2 大权值为 3，该权值的重复次数为 2，输出 3 2。

    （6）2 3 6 5：将 3-6 路径上所有节点的权值都修改为 5。

    （7）4 3 6：查询 3-6 路径上的第 2 大权值和该权值的重复次数，路径 3-6 上的所有权值都相同，输出“ALL SAME”。

    五 分析

    本问题为动态树问题，包括删边/连边、区间更新、区间修改、区间第 2 大值查询。

    六 算法设计

    1 删边/连边

    删除一条边 x -y ，然后添加一条新边 a -b 。只需执行 cut(x , y)、link(a , b)即可。

    2 区间更新

    将 a -b 路径上所有节点的权值都修改为 x 。首先执行 split(a , b)，切分出 a -b 路径，然后执行 change(b , x )，将以 b 为根的子树上的所有节点都修改为x（打懒标记）。

    3 区间修改

    将 a -b 路径上所有节点的权值都增加 d 。首先执行 split(a , b)，切分出 a -b 路径，然后执行 addval(b , d)，将以 b 为根的子树上的所有节点都增加d（打懒标记）。

    4 区间第2大值查询。

    查询 a -b 路径上所有节点的第 2 大权值及该权值出现的次数。首先执行split(a , b)，切分出 a-b 路径，然后执行 query(a , b)，若第2大值的重复次数等于以 y 为根的子树大小，则输出“ALL SAME”，否则输出第 2 大值及其重复次数。

    七 代码

    1. package com.platform.modules.alg.alglib.hdu5002;
    2.  
    3. /**
    4. * @className: Hdu5002
    5. * @description: 参考 http://hzwer.com/5540.html
    6. * @date: 2022/11/17
    7. * @author: chengqiuming
    8. */
    9. public class Hdu5002 {
    10.     private int inf = 0x3f3f3f3f;
    11.     private int N = 100005;
    12.  
    13.     int n, m, top;
    14.     int c[][] = new int[N][2];
    15.     int fa[] = new int[N];
    16.     int v[] = new int[N];
    17.     int st[] = new int[N];
    18.     int mx1[] = new int[N]; // 最大值
    19.     int mx2[] = new int[N]; // 次大值
    20.     int c1[] = new int[N];  // 两者的重复次数
    21.     int c2[] = new int[N];  // 子树大小
    22.     int size[] = new int[N]; // 子树大小
    23.     int ta[] = new int[N]; // 增加懒标记
    24.     int tc[] = new int[N]; // 修改懒标记
    25.     int rev[] = new int[N]; // 反转懒标记
    26.  
    27.     public String output = "";
    28.  
    29.     // 统计 x 的子树中最大、次大值和重复次数，当前节点值为 val,其重复次数为 c
    30.     void cnt(int x, int val, int c) {
    31.         if (val > mx1[x]) {
    32.             mx2[x] = mx1[x];
    33.             mx1[x] = val;
    34.             c2[x] = c1[x];
    35.             c1[x] = c;
    36.         } else if (val == mx1[x]) {
    37.             c1[x] += c;
    38.         } else if (val > mx2[x]) {
    39.             mx2[x] = val;
    40.             c2[x] = c;
    41.         } else if (val == mx2[x]) {
    42.             c2[x] += c;
    43.         }
    44.     }
    45.  
    46.     // y 为根的子树上所有节点改为 val
    47.     void change(int y, int val) {
    48.         mx1[y] = val;
    49.         v[y] = val;
    50.         c1[y] = size[y];
    51.         mx2[y] = -inf;
    52.         c2[y] = 0;
    53.         tc[y] = val;
    54.         if (ta[y] != 0) ta[y] = 0;
    55.     }
    56.  
    57.     // y 为根的子树上所有节点加 val
    58.     void addval(int y, int val) {
    59.         ta[y] += val;
    60.         mx1[y] += val;
    61.         v[y] += val;
    62.         if (mx2[y] != -inf) mx2[y] += val;
    63.     }
    64.  
    65.     void update(int x) {
    66.         int l = c[x][0], r = c[x][1];
    67.         mx1[x] = mx2[x] = -inf;
    68.         c1[x] = c2[x] = 0;
    69.         cnt(x, v[x], 1);
    70.         if (l > 0) {
    71.             cnt(x, mx1[l], c1[l]);
    72.             cnt(x, mx2[l], c2[l]);
    73.         }
    74.         if (r > 0) {
    75.             cnt(x, mx1[r], c1[r]);
    76.             cnt(x, mx2[r], c2[r]);
    77.         }
    78.         size[x] = size[l] + size[r] + 1;
    79.     }
    80.  
    81.     void pushdown(int x) {
    82.         int l = c[x][0], r = c[x][1];
    83.         if (rev[x] == 1) {//反转
    84.             rev[x] ^= 1;
    85.             rev[l] ^= 1;
    86.             rev[r] ^= 1;
    87.             // 交换两者的值，不要写l,r
    88.             int temp = c[x][0];
    89.             c[x][0] = c[x][1];
    90.             c[x][1] = temp;
    91.         }
    92.         if (tc[x] != -inf) {//修改
    93.             if (l > 0) change(l, tc[x]);
    94.             if (r > 0) change(r, tc[x]);
    95.             tc[x] = -inf;
    96.         }
    97.         if (ta[x] != 0) {//增加
    98.             if (l > 0) addval(l, ta[x]);
    99.             if (r > 0) addval(r, ta[x]);
    100.             ta[x] = 0;
    101.         }
    102.     }
    103.  
    104.     boolean isroot(int x) {
    105.         return c[fa[x]][0] != x && c[fa[x]][1] != x;
    106.     }
    107.  
    108.     void rotate(int x) {
    109.         int y = fa[x], z = fa[y], l, r;
    110.         if (c[y][0] == x) l = 0;
    111.         else l = 1;
    112.         r = l ^ 1;
    113.         if (!isroot(y)) {
    114.             if (c[z][0] == y) c[z][0] = x;
    115.             else c[z][1] = x;
    116.         }
    117.         fa[x] = z;
    118.         fa[y] = x;
    119.         fa[c[x][r]] = y;
    120.         c[y][l] = c[x][r];
    121.         c[x][r] = y;
    122.         update(y);
    123.         update(x);
    124.     }
    125.  
    126.     void splay(int x) {
    127.         top = 0;
    128.         st[++top] = x;
    129.         for (int i = x; !isroot(i); i = fa[i])
    130.             st[++top] = fa[i];
    131.         while (top > 0) pushdown(st[top--]);
    132.         while (!isroot(x)) {
    133.             int y = fa[x], z = fa[y];
    134.             if (!isroot(y)) {
    135.                 if (c[y][0] == x ^ c[z][0] == y) {
    136.                     rotate(x);
    137.                 } else {
    138.                     rotate(y);
    139.                 }
    140.             }
    141.             rotate(x);
    142.         }
    143.     }
    144.  
    145.     void access(int x) {
    146.         for (int t = 0; x > 0; t = x, x = fa[x]) {
    147.             splay(x);
    148.             c[x][1] = t;
    149.             update(x);
    150.         }
    151.     }
    152.  
    153.     void makeroot(int x) {
    154.         access(x);
    155.         splay(x);
    156.         rev[x] ^= 1;
    157.     }
    158.  
    159.     void link(int x, int y) {
    160.         makeroot(x);
    161.         fa[x] = y;
    162.     }
    163.  
    164.     void split(int x, int y) {
    165.         makeroot(x);
    166.         access(y);
    167.         splay(y);
    168.     }
    169.  
    170.     void cut(int x, int y) {
    171.         split(x, y);
    172.         c[y][0] = fa[c[y][0]] = 0;
    173.         update(y);
    174.     }
    175.  
    176.     int findroot(int x) {
    177.         access(x);
    178.         splay(x);
    179.         while (c[x][0] > 0) x = c[x][0];
    180.         return x;
    181.     }
    182.  
    183.     void query(int x, int y) {
    184.         if (c1[y] == size[y]) {
    185.             output += "ALL SAME";
    186.         } else {
    187.             output += mx2[y] + " " + c2[y] + "\n";
    188.         }
    189.     }
    190.  
    191.     public String cal(String input) {
    192.         int opt, x, y, a, b, d;
    193.         String[] line = input.split("\n");
    194.  
    195.         String[] num = line[0].split(" ");
    196.         n = Integer.parseInt(num[0]);
    197.         m = Integer.parseInt(num[1]);
    198.         String[] wage = line[1].split(" ");
    199.         for (int i = 1; i <= n; i++) {
    200.             v[i] = Integer.parseInt(wage[i - 1]);
    201.         }
    202.  
    203.         for (int i = 1; i <= n; i++) {
    204.             mx1[i] = v[i];
    205.             c1[i] = 1;
    206.             mx2[i] = -inf;
    207.             c2[i] = 0;
    208.             size[i] = 1;
    209.         }
    210.         for (int i = 1; i <= n; i++) {
    211.             fa[i] = c[i][0] = c[i][1] = 0;
    212.             ta[i] = rev[i] = 0;
    213.             tc[i] = -inf;
    214.         }
    215.         for (int i = 1; i < n; i++) {
    216.             String[] edge = line[i + 1].split(" ");
    217.             x = Integer.parseInt(edge[0]);
    218.             y = Integer.parseInt(edge[1]);
    219.             link(x, y);
    220.         }
    221.         int count = 1;
    222.         while (m-- > 0) {
    223.             String[] query = line[n + count++].split(" ");
    224.             opt = Integer.parseInt(query[0]);
    225.             if (opt == 1) {
    226.                 x = Integer.parseInt(query[1]);
    227.                 y = Integer.parseInt(query[2]);
    228.                 a = Integer.parseInt(query[3]);
    229.                 b = Integer.parseInt(query[4]);
    230.                 cut(x, y);
    231.                 link(a, b);
    232.             } else if (opt == 2) {
    233.                 a = Integer.parseInt(query[1]);
    234.                 b = Integer.parseInt(query[2]);
    235.                 x = Integer.parseInt(query[3]);
    236.                 split(a, b);
    237.                 change(b, x);
    238.             } else if (opt == 3) {
    239.                 a = Integer.parseInt(query[1]);
    240.                 b = Integer.parseInt(query[2]);
    241.                 d = Integer.parseInt(query[3]);
    242.                 split(a, b);
    243.                 addval(b, d);
    244.             } else {
    245.                 a = Integer.parseInt(query[1]);
    246.                 b = Integer.parseInt(query[2]);
    247.                 split(a, b);
    248.                 query(a, b);
    249.             }
    250.         }
    251.  
    252.         return output;
    253.     }
    254. }

    八 测试

    1 输入

    7 7

    5 3 2 1 7 3 6

    1 2

    1 3

    3 4

    3 5

    4 6

    4 7

    4 2 6

    3 4 5 -1

    4 5 7

    1 3 4 2 4

    4 3 6

    2 3 6 5

    4 3 6

    2 输出

  • 相关阅读:
    面向防疫的智能导诊机器人关键技术及应用
    Dagger2系列详解(三)：@privider 依赖
    2022上海生物发酵展-品牌企业纷纷入驻抢占先机，谁来赴盛宴参邀您的参与
    【附源码】计算机毕业设计JAVA家装建材网
    UNIAPP day_03(9.1)服务器端数据的异步请求
    医护上门系统—为老人和患者提供更舒适和现代化体验
    IO流高级流
    基于JAVA高校共享单车管理系统计算机毕业设计源码+数据库+lw文档+系统+部署
    聊聊秒杀系统的设计（一）
    嵌入式：驱动开发 Day2
  • 原文地址：https://blog.csdn.net/chengqiuming/article/details/127904217