首页 > 其他分享 >P3345 [ZJOI2015] 幻想乡战略游戏

P3345 [ZJOI2015] 幻想乡战略游戏

时间:2024-04-15 17:24:04浏览次数:27  
标签:幻想 int siz sum 幽香 times ZJOI2015 P3345 dis

题意:

傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。

在打仗之前,幽香现在面临一个非常基本的管理问题需要解决。

整个地图是一个树结构,一共有 \(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

相关文章

  • P3344 [ZJOI2015] 幻想乡 Wi-Fi 搭建计划
    非常精妙的一个做法。简化题意:定义合法区域为\(y\in[0,R]\)的区域,给定一些在合法区域内的标记点,与一些圆心在合法区域外的,半径为\(R\)的圆,选择第\(i\)个圆会产生\(c_i\)的代价。第一问是最多能覆盖几个标记点;第二问是在保证覆盖标记点最多的情况下,代价的最小值。首先......
  • 论伊甸园幻想
    荣格说,人的人格发展阶段分为三个部分,涵容,调整,中心化。或者说母性,父性和自我性涵容,我们被支持,被喜爱,我们就好像活在伊甸园中周围的环境都是温暖,安全有序的,而到了调整阶段,我们从温柔乡中离开,逐渐认识到外部环境的凶险,我们被迫要去适应社会,迎接现实挑战。而到了中心化阶段,我们的可......
  • 2.17 闲话 & solution『登陆宇宙/带着你所幻想的所有/灵魂加速失控 』
    拜谢了,您别Fake了,您当年自愿退出国集我是极力反对的,我知道您从小学一年级开始打NOI并且直接获得了金牌分数线上的好成绩,肆意AK了好几年NOI,直到近年才意识到自己太过强大只好肆意控分,NOIP2023的题目您当时拿到的一瞬间用\(\frac{2}{3}s\)就全部想到了正解,并在\(\frac{3}{2}......
  • 2.4闲话 & solution - 『登陆宇宙/带着你所幻想的所有』
    \(\text{ARC}\)明天再改\(\text{solution}-『\textbf{AtCoderABC339}』\)比赛被骂的好惨QAQ,但是确实抽象,有点过于简单了,但凡看一眼F题和G题也不至于就过这几道题哈哈今天放ABC的改题来水闲话,不然我集训纪要就没得写了ABC339摘下头上紧箍的发带纠结的心散到九霄外提起......
  • 2.1闲话 - 『奏起我的幻想曲』
    打算换个闲话风格,现在的看起来非常不好今天手滑交了个图片上去卡住了评测集导致被D了漆黑的夜古城之中遗失的传说漆黑的翼苏醒之后陌生的轮廓是谁在我的身后呼唤一时的怔忪是谁在我的心中呼唤为何不将一切掌控快速傅立叶之二我们可以进行卷积的式子标准形......
  • P8883 幻想中成为原神
    (题目传送门)这道题重点就在于“他允许你的答案与真正的答案有着不超过\(2\times10^4\)的绝对误差”,从此可以引申出两种方法。法一由于误差较大,我们可以直接算概率。我们考虑问题的反面,即有多少个数不是完全平方数的倍数。对于一个质数\(p\),一个数是\(p^2\)倍数的概率......
  • 【行云流水线】满足你对工作流编排的一切幻想~skr
    流水线模型众所周知,DevOps流水线(DevOpspipeline)的本质是实现自动化工作流程,用于支持软件开发、测试和部署的连续集成、交付和部署(CI/CD)实践。它是DevOps方法论的核心组成部分,旨在加速软件交付、提高质量和实现持续改进。流水线的核心是流水线模型,是实现工作流编排,执行的重要基石......
  • 终级幻想
    人类对空间的理解是3维,有没有一种可能,空间是3维+(出现和消失)?(这是几维呢?)人类感觉两种重要的方式是眼看和手摸。人之所以能看见物体,是因为物体能反射可见光,如果一个物体不能反射可见光,那我们就看不见了。打个比喩,光能在空气中自由穿梭,一般空气是不能反射可见光的(实际情况是空气中......
  • [ZJOI2015] 地震后的幻想乡积分题解
    题意:给定一个无向图,边权为\([0,1]\)之间的随机变量。求图最小生成树最大边权的期望。\(n\le10\)。Soluion:Meatherm口诏:我都不知道这个东西怎么想出来的针对这道题,好像正常的方法是转计数然后斯特林反演+dp。但是如果想到概率理论,你就已经赢了很遗憾,我没想出来设最大边......
  • ZJOI2015 地震后的幻想乡
    「ZJOI2015」地震后的幻想乡前言:想了很久,最后只能失败告终。基本分析到了一半,只是没有将其转化为古典概型后考虑求解方案数。说实话有点可惜……题意:给定一张\(n\)个点\(m\)条边的无向连通图,每条边的边权是\([0,1]\)之间的随机实数,求其最小生成树上最大边权的期望值......