[SOJ615] 小$\omega$的树【Kruskal重构树】【树链剖分】【分块】

$毒瘤 qwq

题意简述：一棵有点权、边权的树，定义一个联通块的权值为联通块里的点权和乘以边权最小值。\(m\)次修改点权，求出每次修改后权值最大的联通块。\(n\leq 3\times 10^5, m\leq 3\times 10^4\)。

建出最大生成树的Kruskal重构树，则对于重构树上的中间节点\(u\)（即原图中的边），包含它的联通块最大权值为子树中叶子节点（即原图中的点）权值和\(s_u\)乘以该节点的边权\(w_u\)。

为了处理修改操作，我们对重构树树链剖分，则对于每个树上节点\(u\)，它的权值为\(w_u\sum_{v \in \text{the light sons of}~u} s_v+w_u\cdot s_{son_u}\)。

发现每个节点\(u\)的权值关于\(s_{son_u}\)都形如\(a\cdot x+b\)的形式，考虑分块维护凸包。

于是就做完了 对于一个块，如果只修改了一部分点的\(s_i\)，则暴力重构凸包，单次修改\(O(\sqrt{n})\)，每次操作最多修改\(\log n\)次。否则打上修改标记后在块上暴力二分，每次二分\(O(\log n)\)，每次操作最多二分\(\sqrt{n}\)次（因为树的深度是\(O(n)\)级别的）。因此总复杂度\(O(m\sqrt{n}\log n)\)。

#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#define R register
#define ll long long
using namespace std;
const int N = 610000;
const double inf = 1e18;

int n, m, a[N], fa[N], ch[N][2], val[N], size[N], son[N], dep[N], top[N], stck[N], tp, B, noBl;
int bel[N], nxtBl[N], topBl[N], add[N];
ll sum[N], ans[N], ansSon[N];
struct edge {
    int x, y, w;
    inline bool operator < (const edge &a) const {
        return w > a.w;
    }
}edg[N];
struct point {
    ll x, y;
    point(ll x = 0, ll y = 0) : x(x), y(y) {}
    inline point operator - (const point &a) const {
        return point(x - a.x, y - a.y);
    }
    inline ll cross(const point &a) const {
        return x * a.y - y * a.x;
    }
};
vector<point> hull[N];

struct findUnionSet {
///
int fa[N];

void init(int n) {
    for (R int i = 1; i <= n; ++i)
        fa[i] = i;
    return;
}

int find(int x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}

void unite(int x, int y) {
    fa[find(x)] = find(y);
    return;
}
///
}fus;

template <class T> inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

void dfs1(int now) {
    size[now] = 1, dep[now] = dep[fa[now]] + 1;
    if (now <= n) return;
    dfs1(ch[now][0]), dfs1(ch[now][1]);
    size[now] += size[ch[now][0]] + size[ch[now][1]];
    son[now] = size[ch[now][0]] > size[ch[now][1]] ? ch[now][0] : ch[now][1];
    return;
}

inline int get(int x) {
    return x == ch[fa[x]][1];
}

inline void buildBl(int ind) {
    hull[ind].clear();
    int st = topBl[ind], sz;
    while (st && bel[st] == ind) {
        sum[st] += add[ind];
        if (st <= n) break;
        point in(val[st], (ll) val[st] * (sum[st] - sum[topBl[nxtBl[ind]]] - add[nxtBl[ind]]));
        while ((sz = hull[ind].size()) >= 2 && (hull[ind][sz - 1] - hull[ind][sz - 2]).cross(in - hull[ind][sz - 1]) >= 0)
            hull[ind].pop_back();
        hull[ind].push_back(in), st = son[st];
    }
    add[ind] = 0;
    return;
}

inline ll calc(int ind) {
    ll x = -sum[topBl[nxtBl[ind]]] - add[nxtBl[ind]];
    if (hull[ind].size() == 0) return 0;
    if (hull[ind].size() == 1) return hull[ind][0].x * -x + hull[ind][0].y;
    int l = 0, r = hull[ind].size() - 1, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (hull[ind][mid + 1].y - hull[ind][mid].y <= x * (hull[ind][mid + 1].x - hull[ind][mid].x))
            r = mid;
        else
            l = mid + 1;
    }
    return hull[ind][l].x * -x + hull[ind][l].y;
}

void dfs2(int now) {
    if (!now) return;
    int tmp = tp + 1, pos = now, flag = 1;
    while (pos)
        stck[++tp] = pos, top[pos] = now, pos = son[pos];
    while (tmp <= tp) {
        topBl[++noBl] = stck[tmp];
        if (son[fa[stck[tmp]]] == stck[tmp]) nxtBl[bel[fa[stck[tmp]]]] = noBl;
        for (R int i = tmp, rt = min(tp, tmp + B - 1); i <= rt; ++i)
            bel[stck[i]] = noBl;
        tmp = min(tp + 1, tmp + B);
    }
    while (flag) {
        if (stck[tp] == now) flag = 0;
        if (tp != tmp) dfs2(ch[stck[tp]][get(son[stck[tp]]) ^ 1]);
        ansSon[bel[stck[tp]]] = max(ansSon[bel[stck[tp]]], ans[bel[ch[stck[tp]][get(son[stck[tp]]) ^ 1]]]);
        if (topBl[bel[stck[tp]]] == stck[tp])
            buildBl(bel[stck[tp]]), ans[bel[stck[tp]]] = max(ansSon[bel[stck[tp]]], max(ans[nxtBl[bel[stck[tp]]]], calc(bel[stck[tp]])));
        --tp;
    }
    return;
}

inline void modifyChain(int x, int w) {
    while (x) {
        ansSon[bel[x]] = -inf;
        for (R int i = topBl[bel[x]]; i && bel[i] == bel[x]; i = son[i]) {
            ansSon[bel[x]] = max(ansSon[bel[x]], ans[bel[ch[i][get(son[i]) ^ 1]]]);
            sum[i] += dep[i] <= dep[x] ? w : 0;
        }
        buildBl(bel[x]);
        ans[bel[x]] = max(ansSon[bel[x]], max(ans[nxtBl[bel[x]]], calc(bel[x])));
        while (top[x] != topBl[bel[x]]) {
            x = fa[topBl[bel[x]]], add[bel[x]] += w;
            ans[bel[x]] = max(ansSon[bel[x]], max(ans[nxtBl[bel[x]]], calc(bel[x])));
        }
        x = fa[top[x]];
    }
    return;
}

int main() {
    int x, y;
    read(n), read(m), B = sqrt(2 * n - 1);
    for (R int i = 1; i <= n; ++i)
        read(a[i]), sum[i] = a[i];
    for (R int i = 1; i < n; ++i)
        read(edg[i].x), read(edg[i].y), read(edg[i].w);
    sort(edg + 1, edg + n), fus.init(2 * n - 1);
    for (R int i = 1; i < n; ++i) {
        int x = fus.find(edg[i].x), y = fus.find(edg[i].y);
        fus.unite(x, i + n), fus.unite(y, i + n);
        fa[x] = i + n, fa[y] = i + n, ch[i + n][0] = x, ch[i + n][1] = y;
        val[i + n] = edg[i].w, sum[i + n] = sum[x] + sum[y];
    }
    dfs1(2 * n - 1), dfs2(2 * n - 1);
    while (m--) {
        read(x), read(y);
        modifyChain(x, y - a[x]), a[x] = y;
        printf("%lld\n", ans[1]);
    }
    return 0;
}

[SOJ615] 小$\omega$的树【Kruskal重构树】【树链剖分】【分块】

原文：https://www.cnblogs.com/suwakow/p/11669436.html