「CF1023F」Mobile Phone Network

标签：html   ++i   tchar   problem   swa   gis   参考   fine   lin   

「CF1023F」Mobile Phone Network

传送门
直接钦定那 \(k\) 条边在最小生成树中，然后把最小生成树树剖一下。
每条其它边的效果就是把该边端点路径上的边的权对该边边权取 \(\min\)。
不会区间取 \(\min\) 的看这里。

参考代码：

#include 
#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' > 1;
    build(lc(p), l, mid), build(rc(p), mid + 1, r);
}

inline void update(int ql, int qr, int v, int p = 1, int l = 1, int r = n) {
    if (ql > 1;
    pushdown(p);
    if (ql  mid) update(ql, qr, v, rc(p), mid + 1, r);
}

inline int query(int id, int p = 1, int l = 1, int r = n) {
    if (l == r) return mn[p];
    int mid = (l + r) >> 1, res;
    pushdown(p);
    if (id  dep[y]) swap(x, y);
    update(dfn[x] + 1, dfn[y], v);
}

int main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(n), read(k), read(m);
    for (rg int i = 1; i 

「CF1023F」Mobile Phone Network

标签：html   ++i   tchar   problem   swa   gis   参考   fine   lin   

原文地址：https://www.cnblogs.com/zsbzsb/p/12231634.html