题解：P3345 [ZJOI 2015] 幻想乡战略游戏

题解：P3345 [ZJOI 2015] 幻想乡战略游戏

DimStar
  2026-03-12 14:53:16 2026-03-12 14:53:16 创建   2026-03-17 15:15:38 2026-03-17 15:15:38 更新      1.4k 字  7 分钟  

头图是傲娇少女早濑优香。

原题链接。

题意

形式化题意：

给定一棵有 个点的无根有权树，给出 个操作，涉及单点点权修改，初始时所有点点权为 。

要求在每一次操作后求出带权重心，并求出以其为根，所有点到它的权值距离之和（也就是最小的到某点的权值距离和），节点 到根的权值距离定义为根节点到 的距离乘 的点权（注意：权值距离与根节点权值无关）

Solution

为了方便，我们将树变为一棵以节点 为根的有根树，以下均在此条件下讨论。

Part 1

「子树权值和大于等于全树权值和的一半」 的点中，「dfs 序最大」 的点，一定是重心。

显然，由于它是 dfs 序最大的，所以它的儿子的子树权值和小于全树权值和的一半，同时，不在它子树中的其余部分权值和也显然小于等于全树权值和的一半。

所以为了维护每个节点的子树权值和，修改点权时就要修改其父链上的节点的子树权值和，使用重链剖分加线段树实现。

查询重心使用线段树二分。

Part 2

求出重心 后，所有点到它的权值距离之和等于 （ 分别表示 到根的距离和 的点权）。

拆式子变成 。

和式的前两项通过记录 和 维护。

第三项可以通过在修改 的点权时，对其父链进行修改，查询时查询 父链上的和。

具体地，我们记录所有点的父边权，修改时加上点权乘父边权，查询时返回累加值之和。

使用重链剖分加线段树实现。

时间复杂度

重链剖分复杂度 ，线段树区间修改查询和线段树二分复杂度 。

修改：跳重链套线段树区间修改，。
查询重心：线段树二分，。
查询权值距离和：跳重链套线段树区间查询，。

总时间复杂度为

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
namespace FastIO
{
    template <typename T>
    inline void read(T &x)
    {
        short neg = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch))
            if (ch == '-')
                neg = -1;
        x = ch - '0';
        while (ch = getchar(), isdigit(ch))
            x = (x << 3) + (x << 1) + (ch ^ '0');
        x *= neg;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args)
    {
        read(x);
        read(args...);
    }
    template <typename T>
    inline void read(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            read(*(begin + i));
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args)
    {
        write(x);
        putchar(' ');
        write(args...);
    }
    template <typename T>
    inline void write(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            write(*(begin + i)), putchar(' ');
    }
}
using namespace FastIO;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
vector<pair<int, int>> grh[100005];
int faw[100005], dis[100005];

namespace Decomposition
{
    int sz[100005];
    int hson[100005];
    int top[100005];
    int fa[100005];
    void dfs1(int u)
    {
        sz[u] = 1;
        for (auto e : grh[u])
        {
            auto [v, w] = e;
            if (v == fa[u])
                continue;
            fa[v] = u, faw[v] = w, dis[v] = dis[u] + w;
            dfs1(v);
            sz[u] += sz[v];
            hson[u] = (sz[hson[u]] > sz[v]) ? hson[u] : v;
        }
    }
    int dfn[100005], rnk[100005], tim;
    void dfs2(int u, int tp)
    {
        top[u] = tp;
        dfn[u] = ++tim;
        rnk[tim] = u;
        if (hson[u])
        {
            dfs2(hson[u], tp);
            for (auto e : grh[u])
            {
                auto [v, w] = e;
                if (v == fa[u] || v == hson[u])
                    continue;
                dfs2(v, v);
            }
        }
    }
    void init()
    {
        dfs1(1);
        dfs2(1, 1);
    }
}
using namespace Decomposition;

class Segment_Tree
{
private:
    int mx[400005], laz[400005];
    LL fwsum[400005], sum[400005];
    void pushdown(int id)
    {
        if (laz[id])
        {
            mx[id << 1] += laz[id];
            laz[id << 1] += laz[id];
            sum[id << 1] += fwsum[id << 1] * laz[id];
            mx[id << 1 | 1] += laz[id];
            laz[id << 1 | 1] += laz[id];
            sum[id << 1 | 1] += fwsum[id << 1 | 1] * laz[id];
            laz[id] = 0;
        }
    }

public:
    void build(int id, int l, int r)
    {
        mx[id] = laz[id] = fwsum[id] = sum[id] = 0;
        if (l == r)
        {
            fwsum[id] = faw[rnk[l]];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        fwsum[id] = fwsum[id << 1] + fwsum[id << 1 | 1];
        return;
    }
    void update(int id, int l, int r, int ql, int qr, LL e)
    {
        if (ql <= l && r <= qr)
        {
            mx[id] += e;
            laz[id] += e;
            sum[id] += fwsum[id] * e;
            return;
        }
        pushdown(id);
        int mid = (l + r) >> 1;
        if (ql <= mid)
            update(id << 1, l, mid, ql, qr, e);
        if (qr > mid)
            update(id << 1 | 1, mid + 1, r, ql, qr, e);
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
        mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
        return;
    }
    LL querysum(int id, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
            return sum[id];
        pushdown(id);
        int mid = (l + r) >> 1;
        LL res = 0;
        if (ql <= mid)
            res += querysum(id << 1, l, mid, ql, qr);
        if (qr > mid)
            res += querysum(id << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }
    int find(int id, int l, int r, int val)
    {
        if (l == r)
            return rnk[l];
        pushdown(id);
        if (mx[id << 1 | 1] >= val)
            return find(id << 1 | 1, ((l + r) >> 1) + 1, r, val);
        else
            return find(id << 1, l, (l + r) >> 1, val);
    }
} tr;

int n, q;

void update(int u, int e)
{
    for (int l = top[u], r = u; l; l = top[fa[l]], r = fa[top[r]])
    {
        tr.update(1, 1, n, dfn[l], dfn[r], e);
    }
}

LL query(int u)
{
    LL ret = 0;
    for (int l = top[u], r = u; l; l = top[fa[l]], r = fa[top[r]])
    {
        ret += tr.querysum(1, 1, n, dfn[l], dfn[r]);
    }
    return ret;
}

void solve()
{
    read(n, q);
    nmf(i, 2, n)
    {
        int ui, vi, wi;
        read(ui, vi, wi);
        grh[ui].emplace_back(vi, wi);
        grh[vi].emplace_back(ui, wi);
    }
    init();
    tr.build(1, 1, n);
    LL sume = 0, sumdis = 0;
    while (q--)
    {
        int u, e;
        read(u, e);
        sume += e;
        sumdis += (LL)dis[u] * e;
        update(u, e);
        int centroid = tr.find(1, 1, n, (sume + 1) / 2);
        write(sume * dis[centroid] + sumdis - 2 * query(centroid)), putchar('\n');
    }
    return;
}
signed main()
{
    solve();
    return 0;
}
  • 标题: 题解：P3345 [ZJOI 2015] 幻想乡战略游戏
  • 作者: DimStar
  • 创建于 : 2026-03-12 14:53:16
  • 更新于 : 2026-03-17 15:15:38
  • 链接: https://dimstar-zhang.github.io/2026/03/12/题解：P3345-ZJOI-2015-幻想乡战略游戏/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
题解：P3345 [ZJOI 2015] 幻想乡战略游戏
  1. 题意
  2. Solution
  3. 时间复杂度
  4. Code