边分治

野性酷女 2021-12-22 16:49 340阅读 0赞

跟点分治差不多的东西，先转二叉，然后找边，分治。可以动态，还听说有个骚操作叫边分树合并...

注意虚点虚边的处理！注意边分治不能善终，\_n = 1的时候特判。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 void rebuild(int x, int f) {
     2     int temp = 0;
     3     for(int i = 0; i < (int)G[x].size(); i++) {
     4         int y = G[x][i];
     5         if(y == f) continue;
     6         if(!temp) {
     7             temp = x;
     8             add(x, y, 1);
     9             add(y, x, 1);
    10         }
    11         else if(i == G[x].size() - 1) {
    12             add(temp, y, 1);
    13             add(y, temp, 1);
    14         }
    15         else {
    16             add(temp, ++cnt, 0);
    17             add(cnt, temp, 0);
    18             val[cnt] = val[temp];
    19             temp = cnt;
    20             add(temp, y, 1);
    21             add(y, temp, 1);
    22         }
    23         rebuild(y, x);
    24     }
    25     return;
    26 }

转二叉

例题：bzoj2870 [最长道路][Link 1]

找到重心边，然后考虑在两边各选取一个点使得它们路径上的最小值 \* 距离最大。

于是把两边的点分别提取出来排序，然后用一个指针扫过去，维护最值即可。

注意距离的处理，跟分治边的虚实有关。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex)
      4 
      5 typedef long long LL;
      6 const int N = 100010, INF = 0x3f3f3f3f;
      7 
      8 struct Edge {
      9     int nex, v, len;
     10     bool vis;
     11 }edge[N << 1]; int tp = 1;
     12 
     13 struct Node {
     14     LL v, d;
     15     Node(LL D = 0, LL V = 0) {
     16         v = V;
     17         d = D;
     18     }
     19     inline bool operator < (const Node &w) const {
     20         return v < w.v;
     21     }
     22 }stk[2][N];
     23 
     24 int e[N], cnt, n, siz[N], d[N], _n, small, root, head[2];
     25 LL val[N], Val[N], ans;
     26 std::vector<int> G[N];
     27 
     28 inline void add(int x, int y, int z) {
     29     tp++;
     30     edge[tp].v = y;
     31     edge[tp].len = z;
     32     edge[tp].nex = e[x];
     33     e[x] = tp;
     34     return;
     35 }
     36 
     37 void rebuild(int x, int f) {
     38     int temp = 0;
     39     for(int i = 0; i < (int)G[x].size(); i++) {
     40         int y = G[x][i];
     41         if(y == f) continue;
     42         if(!temp) {
     43             temp = x;
     44             add(x, y, 1);
     45             add(y, x, 1);
     46         }
     47         else if(i == G[x].size() - 1) {
     48             add(temp, y, 1);
     49             add(y, temp, 1);
     50         }
     51         else {
     52             add(temp, ++cnt, 0);
     53             add(cnt, temp, 0);
     54             val[cnt] = val[temp];
     55             temp = cnt;
     56             add(temp, y, 1);
     57             add(y, temp, 1);
     58         }
     59         rebuild(y, x);
     60     }
     61     return;
     62 }
     63 
     64 void getroot(int x, int f) {
     65     siz[x] = 1;
     66     forson(x, i) {
     67         int y = edge[i].v;
     68         if(y == f || edge[i].vis) continue;
     69         getroot(y, x);
     70         if(std::max(siz[y], _n - siz[y]) < small) {
     71             small = std::max(siz[y], _n - siz[y]);
     72             root = i;
     73         }
     74         siz[x] += siz[y];
     75     }
     76     return;
     77 }
     78 
     79 void DFS_1(int x, int f, int flag) {
     80     siz[x] = 1;
     81     Val[x] = std::min(val[x], Val[f]);
     82     //printf("x = %d d = %d Val = %lld \n", x, d[x], Val[x]);
     83     stk[flag][++head[flag]] = Node(d[x], Val[x]);
     84     forson(x, i) {
     85         int y = edge[i].v;
     86         if(y == f || edge[i].vis) continue;
     87         d[y] = d[x] + edge[i].len;
     88         DFS_1(y, x, flag);
     89         siz[x] += siz[y];
     90     }
     91     return;
     92 }
     93 
     94 void e_div(int x) {
     95     if(_n == 1) return;
     96     small = INF;
     97     getroot(x, 0);
     98     edge[root].vis = edge[root ^ 1].vis = 1;
     99 
    100     x = edge[root].v;
    101     int y = edge[root ^ 1].v;
    102     //printf("div x = %d y = %d \n", x, y);
    103 
    104     head[0] = head[1] = 0;
    105     d[x] = d[y] = 0;
    106     DFS_1(x, 0, 0);
    107     DFS_1(y, 0, 1);
    108     std::sort(stk[0] + 1, stk[0] + head[0] + 1);
    109     std::sort(stk[1] + 1, stk[1] + head[1] + 1);
    110 
    111     int p1 = head[1];
    112     LL large = -INF;
    113     for(int i = head[0]; i >= 1; i--) {
    114         while(p1 && stk[1][p1].v >= stk[0][i].v) {
    115             large = std::max(large, stk[1][p1].d);
    116             p1--;
    117         }
    118         ans = std::max(ans, stk[0][i].v * (stk[0][i].d + large + edge[root].len + 1));
    119     }
    120     large = -INF;
    121     p1 = head[0];
    122     for(int i = head[1]; i >= 1; i--) {
    123         while(p1 && stk[0][p1].v >= stk[1][i].v) {
    124             large = std::max(large, stk[0][p1].d);
    125             p1--;
    126         }
    127         ans = std::max(ans, stk[1][i].v * (stk[1][i].d + large + edge[root].len + 1));
    128     }
    129     //printf("ans = %lld \n", ans);
    130     _n = siz[x];
    131     e_div(x);
    132     _n = siz[y];
    133     e_div(y);
    134     return;
    135 }
    136 /*
    137 3
    138 5 3 5
    139 1 2
    140 1 3
    141 */
    142 
    143 void out(int x, int f) {
    144     printf("x = %d f = %d  val = %lld\n", x, f, val[x]);
    145     forson(x, i) {
    146         int y = edge[i].v;
    147         if(y == f) continue;
    148         //printf("%d -> %d \n", x, y);
    149         out(y, x);
    150     }
    151     return;
    152 }
    153 
    154 int main() {
    155 
    156     Val[0] = INF;
    157     scanf("%d", &n);
    158     for(int i = 1; i <= n; i++) {
    159         scanf("%lld", &val[i]);
    160         ans = std::max(ans, val[i]);
    161     }
    162     for(int i = 1, x, y; i < n; i++) {
    163         scanf("%d%d", &x, &y);
    164         G[x].push_back(y);
    165         G[y].push_back(x);
    166     }
    167     cnt = n;
    168     rebuild(1, 0);
    169 
    170     //out(1, 0);
    171     _n = cnt;
    172     e_div(1);
    173     printf("%lld\n", ans);
    174     return 0;
    175 }

AC代码

例题：[暴力写挂][Link 2]。[通道][Link 3]。

转载于:https://www.cnblogs.com/huyufeifei/p/10706521.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/53dd0a4de7044602b14fbbd9565e98de.png
[Link 1]: https://www.cnblogs.com/huyufeifei/p/10706443.html
[Link 2]: https://www.cnblogs.com/huyufeifei/p/10714846.html
[Link 3]: https://www.cnblogs.com/huyufeifei/p/10718003.html