题解 P3345 【[ZJOI2015]幻想乡战略游戏】

kai586123 · 2019-07-29 20:26:43 · 题解

其他题解都是动态点分治，这篇题解是用线段树+树剖的。

欢迎来我的Blog来看：[ZJOI2015] 幻想乡战略游戏

先上个复杂度吧：修改O(nlog^2n)，查询O(nlogn)，截止到发题解是最优解第二名

一个结论： 本题中，重心位置和点权，边权无关

看起来不可思议吧。

证明：

我们可以换一种方式计算答案。枚举边edge_i，这条边把树分为两部分。它的两端点是x_i,y_i，两子树的大小为size_x,size_y，那么有：

通过直接构造出重心位置，并证明其它位置不比它更优证明结论：

在树上选一个点，使得它最大的子树大小（子树内军队数量）最小。这个点就是重心。

可以任选一个其它点，计算出以这个点为补给站的答案。考虑把选择的点向重心移动一条边对答案的影响。这条边是edge，两边为x,y，大小分别为size_x,size_y。从x走到y。

由推导出的新计算式，只有移动经过的这条边对答案产生的贡献发生了变化，是：

显然，因为这个点不在我们选出的重心，size_y不可能小于size_x，即，让答案更优了。

实际上，这个点和普通不带权树的重心位置一样。

快速找到重心

在树上找到一个点x，满足size_{root} \leq size_x * 2，且x最深。

这个结合普通树重心性质很容易得出。

线段树叶子维护子树大小，其他节点维护线段树上子节点大小最大值。查询的时候在线段树上二分。

求答案

前两个随便维护，重点是第三个。

令点权为w_x=edge(x,fa(x))，每次修改一个点的时候，就把它到根的大小size全部加上修改的值。查询重心到根，每个点size_x * w_x。

这是因为两个点到lca到根的路径，是两个点到根的共同路径。

#include <bits/stdc++.h>
typedef long long LL;

inline int rd() {
    int a = 1, b = 0; char c = getchar();
    while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
    while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
    return a ? b : -b;
}

const int N = 1e5 + 233;
int n, m;

struct Graph { int to, nxt, cost; } g[N * 2];
int head[N], tot;

inline void addedge(int x, int y, int c) {
    g[++tot].to = y, g[tot].nxt = head[x],
    g[tot].cost = c, head[x] = tot;
}

int fa[N], son[N], size[N], dep[N], dis[N];
int top[N], id[N], wh[N], wt[N], num;

void dfs1(int x) {
    for (int i = head[x]; i; i = g[i].nxt) {
        int y = g[i].to;
        if (y != fa[x]) {
            fa[y] = x; dep[y] = dep[x] + 1;
            dis[y] = dis[x] + g[i].cost;
            size[y] = 1;
            dfs1(y);
            if (size[son[x]] < size[y])
                son[x] = y;
            size[x] += size[y];
        }
    }
}

void dfs2(int x, int topf) {
    top[x] = topf; id[x] = ++num; wh[num] = x;
    wt[num] = dis[x] - dis[fa[x]];
    if (son[x]) {
        dfs2(son[x], topf);
        for (int i = head[x]; i; i = g[i].nxt) {
            int y = g[i].to;
            if (y != fa[x] && y != son[x])
                dfs2(y, y);
        }
    }
}

#define ls(p) p << 1
#define rs(p) p << 1 | 1

int sz[N * 4], tag[N * 4];
LL edge[N * 4], sum[N * 4];

void build(int p, int L, int R) {
    if (L == R) {
        edge[p] = wt[L];
        return;
    }
    int mid = (L + R) >> 1;
    build(ls(p), L, mid);
    build(rs(p), mid + 1, R);
    edge[p] = edge[ls(p)] + edge[rs(p)];
}

inline void pushup(int p) {
    sz[p] = std::max(sz[ls(p)], sz[rs(p)]);
    sum[p] = sum[ls(p)] + sum[rs(p)];
}

inline void pushdown(int p) {
    if (tag[p]) {
        sz[ls(p)] += tag[p];
        sz[rs(p)] += tag[p];
        tag[ls(p)] += tag[p];
        tag[rs(p)] += tag[p];
        sum[ls(p)] += (LL)tag[p] * edge[ls(p)];
        sum[rs(p)] += (LL)tag[p] * edge[rs(p)];
        tag[p] = 0;
    }
}

void add(int p, int l, int r, int v, int L, int R) {
    if (l <= L && r >= R) {
        sz[p] += v; tag[p] += v;
        sum[p] += (LL)v * edge[p];
        return;
    }
    pushdown(p);
    int mid = (L + R) >> 1;
    if (l <= mid)
        add(ls(p), l, r, v, L, mid);
    if (r > mid)
        add(rs(p), l, r, v, mid + 1, R);
    pushup(p);
}

LL query(int p, int l, int r, int L, int R) {
    if (l <= L && r >= R)
        return sum[p];
    pushdown(p);
    int mid = (L + R) >> 1;
    LL ret = 0;
    if (l <= mid)
        ret += query(ls(p), l, r, L, mid);
    if (r > mid)
        ret += query(rs(p), l, r, mid + 1, R);
    return ret;
}

inline int weight() {
    int p = 1, L = 1, R = n;
    while (L < R) {
        pushdown(p);
        int mid = (L + R) >> 1;
        if (sz[rs(p)] * 2 >= sz[1])
            L = mid + 1, p = rs(p);
        else R = mid, p = ls(p);
    }
    return wh[L];
}

inline void range_add(int x, int y) {
    while (top[x] != 1) {
        add(1, id[top[x]], id[x], y, 1, n);
        x = fa[top[x]];
    }
    add(1, 1, id[x], y, 1, n);
}

inline LL range_query(int x) {
    LL ret = 0;
    while (top[x] != 1) {
        ret += query(1, id[top[x]], id[x], 1, n);
        x = fa[top[x]];
    }
    return ret + query(1, 1, id[x], 1, n);
}

LL sum_dis_e, sum_e;

inline LL getans(int x) {
    return sum_dis_e + dis[x] * sum_e - 2 * range_query(x);
}

int main() {
    n = rd(); m = rd();
    for (int i = 1; i < n; ++i) {
        int x = rd(), y = rd(), c = rd();
        addedge(x, y, c);
        addedge(y, x, c);
    }

    dfs1(1); dfs2(1, 1);
    build(1, 1, n);

    while (m--) {
        int x = rd(), y = rd();
        sum_e += y;
        sum_dis_e += (LL)dis[x] * y;
        range_add(x, y);
        printf("%lld\n", getans(weight()));
    }
    return 0;
}