题意:
傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。
在打仗之前,幽香现在面临一个非常基本的管理问题需要解决。
整个地图是一个树结构,一共有 \(n\) 块空地,这些空地被 \(n-1\) 条带权边连接起来,使得每两个点之间有一条唯一的路径将它们连接起来。
在游戏中,幽香可能在空地上增加或者减少一些军队。同时,幽香可以在一个空地上放置一个补给站。如果补给站在点 \(u\) 上,并且空地 \(v\) 上有 \(d_v\) 个单位的军队,那么幽香每天就要花费 \(d_v \times \text{dist}(u,v)\) 的金钱来补给这些军队。由于幽香需要补给所有的军队,因此幽香总共就要花费为 \(\sum (d_v \times \text{dist}(u,v))\)(其中 \(1 \leq v \leq N\))的代价,\(\text{dist}(u,v)\) 表示 \(u\) 和 \(v\) 在树上的距离(唯一路径的权和)。
因为游戏的规定,幽香只能选择一个空地作为补给站。在游戏的过程中,幽香可能会在某些空地上制造一些军队,也可能会减少某些空地上的军队,进行了这样的操作以后,出于经济上的考虑,幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了,幽香无法轻易的进行最优的安排,你能帮帮她吗?
你可以假定一开始所有空地上都没有军队。
分析:
以补给点 \(rt\) 为根的代价为 \(\sum_{i=1}^{n} siz_{i} \times (siz_{rt} - siz_{i}) \times w_{i}\),其中 \(siz_{i}=\sum_{v \in subtree(i)}a_{v}\),\(w_{i}\) 表示 \(i\) 的父亲到 \(i\) 的边权。
可以发现当 \(rt\) 为整棵树的带权重心时最优,证明如下:
考虑从补给点从 \(y\) 移动到 \(y\) 的父亲 \(x\),对代价带来的影响。显然有:
\[\Delta = siz_{y} \times w_{y} - (siz_{rt} - siz_{y}) \times w_{y} \]考虑 \(rt\) 的一个儿子 \(son\),根据重心的性质 \(2siz_{son} \le siz_{rt}\)。那么总有 \(2siz_{y} \le siz_{rt}\)。
因此往补给点往 \(rt\) 移动不会更劣。
如何动态维护带权重心的位置呢?
选 \(1\) 为根。那么 \(x\) 为重心的一个必要条件为 \(2(siz_{1}-siz_{x}) \le siz_{1}\),即 \(2siz_{x} \ge siz_{1}\)。
假如 \(x\) 满足这个条件,不难发现最后重心的位置一定是在 \(x\) 子树内。
因此可以归纳出:满足 \(2siz_{x} \ge siz_{1}\) 的深度最深的 \(x\) 一定为重心。
又因为满足条件的 \(x\) 肯定是 \(1\) 所在重链的一段前缀,所以深度具有单调性。线段树二分即可。
现在的问题是:已知补给点的位置 \(x\),计算它的代价。
套路地拆开这个式子(\(dis_{i}\) 表示根到 \(i\) 的路径边权和):
\[\begin{aligned} ans &=\sum_{i=1}^{n}a_{i} \times \text{dist}(i,x)\\ &=\sum_{i=1}^{n}a_{i} \times (dis_{i}+dis_{x}-2\times dis_{\text{lca}(i,x)} \\ &=\sum_{i=1}^{n}a_{i} \times dis_{i} + dis_{x} \times \sum_{i=1}^{n}a_{i}-2\times \sum_{i=1}^{n} a_{i} \times dis_{\text{lca}(i,x)} \end{aligned} \]对于 \(\sum_{i=1}^{n} a_{i} \times dis_{\text{lca}(i,x)}\)。
将 a[x] += y
时,把 \(x\) 到根节点的路径上的 \(siz_{i}\) 都加上 \(y\)。
那么 \(\sum_{i=1}^{n} a_{i} \times dis_{\text{lca}(i,x)}\) 就等于 \(\sum_{i \in (1 \rightarrow x)} siz_{i} \times w_{i}\)。
树链剖分即可,时间复杂度 \(O(n+ Q \log^2 n)\)。
代码:
#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int n, Q, Siz1;
struct edge {
int to, w;
};
vector<edge>p[N];
int dis[N], P[N], P2[N], top[N], son[N], dfn[N], siz[N], father[N], id[N], tot;
int S[N * 4], W[N * 4], sum[N * 4], tag[N * 4];
void dfs1(int x, int fa) {
father[x] = fa;
siz[x] = 1;
int Maxson = -1;
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i].to;
if(y == fa) continue;
dis[y] = dis[x] + p[x][i].w;
P[y] = p[x][i].w;
dfs1(y, x);
siz[x] += siz[y];
if(siz[y] > Maxson) {
Maxson = siz[y];
son[x] = y;
}
}
}
void dfs2(int x, int topf) {
top[x] = topf;
dfn[x] = ++tot;
P2[tot] = P[x];
id[tot] = x;
if(!son[x]) return;
dfs2(son[x], topf);
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i].to;
if(top[y]) continue;
dfs2(y, y);
}
}
void pushup(int u) {
W[u] = W[u * 2] + W[u * 2 + 1];
sum[u] = sum[u * 2] + sum[u * 2 + 1];
S[u] = max(S[u * 2], S[u * 2 + 1]);
}
void build(int u, int L, int R) {
if(L == R) {
W[u] = P2[L];
return;
}
int mid = (L + R) / 2;
build(u * 2, L, mid);
build(u * 2 + 1, mid + 1, R);
pushup(u);
}
void maketag(int u, int s) {
S[u] += s;
sum[u] += W[u] * s;
tag[u] += s;
}
void pushdown(int u) {
maketag(u * 2, tag[u]);
maketag(u * 2 + 1, tag[u]);
tag[u] = 0;
}
void update(int u, int L, int R, int l, int r, int s) {
if(R < l || r < L) return;
if(l <= L && R <= r) {
maketag(u, s);
return;
}
pushdown(u);
int mid = (L + R) / 2;
update(u * 2, L, mid, l, r, s);
update(u * 2 + 1, mid + 1, R, l, r, s);
pushup(u);
}
int query_s(int u, int L, int R, int l, int r) {
if(R < l || r < L) return 0;
if(l <= L && R <= r) return sum[u];
pushdown(u);
int mid = (L + R) / 2;
return query_s(u * 2, L, mid, l, r) + query_s(u * 2 + 1, mid + 1, R, l, r);
}
void Add_Tree(int x, int s) { //[x->1]这条路径加上s
while(x) {
update(1, 1, n, dfn[top[x]], dfn[x], s);
x = father[top[x]];
}
}
int Ask_Tree(int x) {
int res = 0;
while(x) {
res += query_s(1, 1, n, dfn[top[x]], dfn[x]);
x = father[top[x]];
}
return res;
}
int query(int u, int L, int R, int x) {
if(L == R) return S[u];
pushdown(u);
int mid = (L + R) / 2;
if(x <= mid) return query(u * 2, L, mid, x);
else return query(u * 2 + 1, mid + 1, R, x);
}
int Find(int u, int L, int R) {
if(L == R) return id[L];
pushdown(u);
int mid = (L + R) / 2;
if(2 * S[u * 2 + 1] >= Siz1) return Find(u * 2 + 1, mid + 1, R);
else return Find(u * 2, L, mid);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> Q;
for(int i = 1, u, v, w; i <= n - 1; i++) {
cin >> u >> v >> w;
p[u].push_back((edge){v, w});
p[v].push_back((edge){u, w});
}
dfs1(1, 0); dfs2(1, 1);
build(1, 1, n);
int sum1 = 0, sum2 = 0, sum3 = 0, Sa = 0;
while(Q--) {
int X, v;
cin >> X >> v;
Add_Tree(X, v);
Siz1 = query(1, 1, n, dfn[1]);
int x = Find(1, 1, n); //重心
sum1 += dis[X] * v;
Sa += v;
sum2 = dis[x] * Sa;
sum3 = 2 * Ask_Tree(x);
cout << sum1 + sum2 - sum3 << endl;
}
return 0;
}
标签:幻想,int,siz,sum,幽香,times,ZJOI2015,P3345,dis
From: https://www.cnblogs.com/xcs123/p/18136512