[ZJOI2015] 幻想乡战略游戏
Problem
傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。
在打仗之前,幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构,一共有 n 块空地,这些空地被 n - 1 条带权边连接起来,使得每两个点之间有一条唯一的路径将它们连接起来。
在游戏中,幽香可能在空地上增加或者减少一些军队。同时,幽香可以在一个空地上放置一个补给站。 如果补给站在点 u 上,并且空地 v 上有 dv 个单位的军队,那么幽香每天就要花费 dv*dist(u,v) 的金钱来补给这些军队。
由于幽香需要补给所有的军队,因此幽香总共就要花费为 Sigma(Dv*dist(u,v), 其中 1 <=V<=N) 的代价。其中 dist(u,v) 表示 u 个 v 在树上的距离(唯一路径的权和)。
因为游戏的规定,幽香只能选择一个空地作为补给站。在游戏的过程中,幽香可能会在某些空地上制造一些军队,也可能会减少某些空地上的军队,进行了这样的操作以后,出于经济上的考虑,幽香往往可以移动他的补给站从而省一些钱。
但是由于这个游戏的地图是在太大了,幽香无法轻易的进行最优的安排,你能帮帮她吗? 你可以假定一开始所有空地上都没有军队。
Solution
本题要求求带权重心。
求到带权重心之后,我们就可以通过带修动态点分治得到我们想要的答案。现在问题就在于怎么求带权重心。
由贪心的思想,求带权重心有个神奇的性质:
假设现在带权重心为 $u$,则该树强制以 $u$ 为根,$f_i$ 为以 $i$ 为根的子树的大小。
当 $2f_s>f_u$(s 为 u 的儿子)的时候,带权重心的范围肯定在以 s 为根的子树的范围内。
利用点分治的性质,在点分树上查询,可以保证每次范围缩小一半,即可以在 $\log n$ 的时间内查询。
现在问题在于,如果在点分树上查询,那么当往子树重点方向行进的话,可能子树的重点的子树并不是完整的。
解决办法是记录每个重点的子树的直接儿子。然后从直接儿子开始在点分树上往上每个点加 $f_u-f_s$ 直到该子树重点。
为什么这样是可行的?
首先我们保证查到的子树是按照深度递增的。也就是说直到直接儿子为止,这里面所有的点都保证了其子树是完整的。
其次保证与不完整的子树相邻。其它的子树都不与不完整的子树相邻,因此是可以不予理会的。直到它与不完整的子树相邻。
比较难解释其实。你甚至可能不懂这上面在说什么,但你可以自己先试着不管这些问题打打。
Code
// Code by ajcxsu
// Problem: battle
#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
template <typename T> void gn(T &x) {
x=0;
T pl=1;
char ch=getchar();
while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
x*=pl;
}
const int N=2e5+10, M=4e5+10;
int h[N], to[M], nexp[M], W[M], p=1;
inline void ins(int a,int b,int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++;}
int n,Q;
ll d[N], tot;
namespace Dis {
int dep[N], son[N], fa[N], siz[N];
int dfn[N], top[N], idx;
ll wdep[N]; // 带权深度
bool vis[N];
void dfs1(int x, int k) {
dep[x]=k, siz[x]=1;
for(int u=h[x];u;u=nexp[u])
if(!dep[to[u]]) {
fa[to[u]]=x;
dfs1(to[u], k+1);
siz[x]+=siz[to[u]];
if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
}
}
void dfs2(int x,int t) {
dfn[x]=++idx, top[x]=t;
if(son[x]) dfs2(son[x], t);
for(int u=h[x];u;u=nexp[u])
if(!dfn[to[u]]) dfs2(to[u], to[u]);
}
int lca(int s,int t) {
while(top[s]!=top[t]) {
if(dep[top[s]]<dep[top[t]]) swap(s,t);
s=fa[top[s]];
}
if(dep[s]>dep[t]) return t;
return s;
}
void dfs3(int x,ll k) {
wdep[x]=k, vis[x]=1;
for(int u=h[x];u;u=nexp[u])
if(!vis[to[u]]) dfs3(to[u], k+W[u]);
}
void init() { dfs1(1,1), dfs2(1,1), dfs3(1,0); }
ll dis(int s, int t) {
int l=lca(s,t);
return wdep[s]+wdep[t]-wdep[l]*2;
}
}
int siz[N], hvy, minn, S;
vector<ll> dt[N], wdt[N], son[N], bson[N]; // 子树点权和, 带权子树点权和, 子树的重点, 子树第一个节点
ll f[N]; // 子树点权总和
bool vis[N];
int fa[N];
void ghvy(int x,int fa) {
siz[x]=1;
int ma=0;
for(int u=h[x];u;u=nexp[u])
if(to[u]!=fa && !vis[to[u]]) {
ghvy(to[u], x);
siz[x]+=siz[to[u]];
ma=max(ma, siz[to[u]]);
}
ma=max(ma, S-siz[x]);
if(ma<minn) minn=ma, hvy=x;
}
void gans(int x) {
vis[x]=1;
for(int u=h[x];u;u=nexp[u])
if(!vis[to[u]]) {
dt[x].push_back(0), wdt[x].push_back(0);
ghvy(to[u],0), S=siz[to[u]], minn=INF, ghvy(to[u],0);
son[x].push_back(hvy), bson[x].push_back(to[u]);
fa[hvy]=x;
gans(hvy);
}
}
void changed(int x,ll add) {
d[x]+=add; f[x]+=add;
int from=x, u=x;
x=fa[x];
while(x) {
for(int i=0;i<dt[x].size();i++)
if(son[x][i]==from) dt[x][i]+=add, wdt[x][i]+=add*Dis::dis(u, x);
f[x]+=add;
from=x, x=fa[x];
}
}
void pushup(int x,ll d,int aim) {
while(x!=aim) {
f[x]+=d;
x=fa[x];
}
f[x]+=d;
}
int Find(int x) {
for(int i=0;i<dt[x].size();i++)
if(f[son[x][i]]*2>f[x]) {
int res;
ll p=f[x]-f[son[x][i]];
pushup(bson[x][i], p, son[x][i]);
res=Find(son[x][i]);
pushup(bson[x][i], -p, son[x][i]);
return res;
}
return x;
}
ll query(int x) {
int from=-1, u=x;
ll dis;
ll ret=0;
while(x) {
dis=Dis::dis(x,u);
for(int i=0;i<dt[x].size();i++)
if(son[x][i]!=from) ret+=wdt[x][i]+dt[x][i]*dis;
ret+=d[x]*dis;
from=x, x=fa[x];
}
return ret;
}
int main() {
gn(n), gn(Q);
for(int i=0,u,v,w;i<n-1;i++) gn(u), gn(v), gn(w), ins(u,v,w), ins(v,u,w);
Dis::init();
int u,e;
gans(1);
while(Q--) {
gn(u), gn(e);
tot+=e;
changed(u, e);
printf("%lld\n", query(Find(1)));
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-3345.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆