文档章节

LOJ #2135. 「ZJOI2015」幻想乡战略游戏(点分树)

o
 osc_1ee7cxmx
发布于 2018/08/06 20:55
字数 1846
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题意

给你一颗 $n$ 个点的树,每个点的度数不超过 $20$ ,有 $q$ 次修改点权的操作。

需要动态维护带权重心,也就是找到一个点 $v$ 使得 $\displaystyle \sum_{v} w_v \times \mathrm{dist}(u, v)$ 最小。

数据范围

$n \le 10^5, q \le 10^5, \forall v, w_v \ge 0$

题解

$\text{Update on 2019.3.29:}$ 似乎可以二叉化就可以不用保证度数了。。

首先了解一个重心的重要性质:

对于一条边 $x \to y$ 如果 $x$ 侧子树和 $>$ $y$ 侧子树和,那么重心一定在 $x$ 侧。

值得一提的是这个结论对于 $\mathrm{dist}^k(x, i)$ 都是成立的,一般情况下都需要快速求出树的带权重心。

利用这个结论可以快速求出 带权重心

暴力求的话,在随机数据下表现非常优秀,但是我们明显可以用一些数据结构来优化这个过程,此时不难想到 点分树

因为对于上面那个找 带权重心 的过程,我们可以考虑分治解决。

  1. 首先先到整棵树的重心,当做分治操作的起点。
  2. 每次考虑枚举它所有点分树上的儿子,然后向着 $sumchild_y * 2 > Sum$ 的方向去走,也就是向着子树权值和大于总权值一半的方向。
  3. 然后我们接下来就可以到这个子树所对应的分治中心,继续进行分治操作。
  4. 直到这个点在点分树上不存在一个儿子满足 $sumchild_y * 2 > Sum$ 的要求,此时这个点就是重心。

这样我们最多重复 $\log n$ 次操作就停下来,接下来我们就是需要动态求一个子树的 $sum_y$ 。

这个显然可以用树剖线段树等数据结构进行维护,但我们有了点分树显然这样是多余的。

我们考虑对于每个点分树上每个点,维护它子树所有点的 $w_i$ 的和,记为 $\displaystyle sum_i = \sum_{v \in child(i)} w_v$ 。

我们每次从 $x \to y$ 向下分治的时候,令 $v$ 为 $x \to y$ 在 原树 路径上除 $x$ 外第一个点。

我们考虑把 $v \to y$ 在点分树路径上的所有 $sum$ 加上 $sum_x - sum_y$ 也就是 $x$ 部分的点权。

至于这样为什么是对的。简单说明下,这样就会对接下来所有需要算上 $x$ 部分贡献的分治重心进行贡献。这样我们就保证了所有要算上的点都是算上的正确的答案。

注意做完后需要减回来。


然后我们找到了重心,考虑计算答案。

有两种方法。

  1. 第一种是类似于 「HNOI2015」开店 其中一个做法,利用满足差分的性质。

    也就是 $\displaystyle \sum {i=1}^{n} w_i \mathrm{dist}(x, i) = \sum{i=1}^{n} w_i(d_i + d_x) - 2 \sum_{i=1}^{n} w_i d_{lca(i, x)}$ 的特性。(此处 $d_i$ 为 $i$ 的深度)

    对于每个点将其到根路径链上的点加上 $w_i$ ,然后询问 $x$ 到根的路径点权和 $res$。

    用 $\displaystyle \sum_{i=1}^{n} w_id_i + (\sum_{i=1}^{n}w_i)d_x$ 减去 $2res$ 就行了。然后用树剖后,利用线段树就可以动态维护了。

  2. 但显然此处,我们还是有着点分树这个强大的树上结构,可以考虑换一种方式来维护。

    我们在之前维护 $sum_u$ 的基础上,多维护两个东西。

    • $tot_u$ :点分树上 $u$ 的子树里所有点的到 $u$ 的带权距离和 $\displaystyle \sum_{v \in child(u)} w_v \times \mathrm{dist}(v, u)$。
    • $totfa_u$ :点分树上$u$ 的子树里所有点的到 $u$ 在点分树上的父亲 $fa$ 的带权距离和 $\displaystyle \sum_{v \in child(u)} w_v \times \mathrm{dist}(v, fa)$。

    然后询问 $pos$ 节点的时候。我们考虑每次在点分树向上跳,并计算贡献。

    假设当前从 $v \to u$ ,把 $ans$ 加上 $(sum_{u} - sum_{v}) \times \mathrm{dist}(pos,u)$ ,这个意思就是把 $v$ 外面所有的点加上这条边权的答案。

    但是这样显然算少了,因为 $v$ 外面所有点到 $u$ 的距离没有算上,所以还要加上 $tot_u - totfa_v$ 这部分贡献就行了。

    注意 $ans$ 一开始的时候初值是 $tot_{pos}$ 。

    然后为了代码没有那么毒瘤,对于此处的树上距离,我们可以预处理出每个点到它点分树上的祖先的距离,因为我们只需要用上这些点对的距离。

总结

对于一些动态有关树上距离的问题,我们可以考虑点分树之类的强大数据结构。

然后带权重心都可以满足之前那个性质,可以用点分树上去找。

代码

强烈建议看看我的代码!! 写的真的优秀!!

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
	int x = 0, fh = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * fh;
}

void File() {
#ifdef zjp_shadow
	freopen ("2135.in", "r", stdin);
	freopen ("2135.out", "w", stdout);
#endif
}

const int N = 1e5 + 1e3, M = N << 1;

typedef long long ll;

int Head[N], Next[M], to[M], val[M], e;
inline void add_edge(int u, int v, int w) {
	to[++ e] = v; Next[e] = Head[u]; Head[u] = e; val[e] = w;
}
inline void Add(int u, int v, int w) {
	add_edge(u, v, w); add_edge(v, u, w);
}

#define Travel(i, u, v) for(register int i = Head[u], v = to[i]; i; v = to[i = Next[i]])

bitset<N> vis;
int sz[N], maxsz[N], rt, nodesum;
void Get_Root(int u, int fa = 0) {
	sz[u] = maxsz[u] = 1;
	Travel(i, u, v) if (v != fa && !vis[v])
		Get_Root(v, u), sz[u] += sz[v], chkmax(maxsz[u], sz[v]);
	chkmax(maxsz[u], nodesum - sz[u]);
	if (maxsz[u] < maxsz[rt]) rt = u;
}

ll dis[N][20]; int from[N], cur[N];
void Get_Dis(int u, ll dep, int fa, int anc) {
	if (fa) from[u] = anc, dis[u][cur[u] ++] = dep;
	Travel(i, u, v) if (!vis[v] && v != fa) Get_Dis(v, dep + val[i], u, anc);
}

typedef pair<int, ll> PII;
#define fir first
#define sec second
#define mp make_pair
vector<PII> Sub[N];

void Dfs_Div(int u = 1) {
	vis[u] = true; Get_Dis(u, 0, 0, u);
	Travel(i, u, v) if (!vis[v])
		rt = 0, nodesum = sz[v], Get_Root(v), 
		   Sub[u].push_back(mp(rt, v)), from[rt] = u, Dfs_Div(rt);
}

ll sum[N], tot[N], tot_fa[N];
inline void Update(int pos, int uv) {
	tot_fa[pos] += dis[pos][0] * uv;
	for (register int u = pos, dep = 0; u; u = from[u], ++ dep) {
		sum[u] += uv;
		tot[from[u]] += dis[pos][dep] * uv;
		tot_fa[from[u]] += dis[pos][dep + 1] * uv;
	}
}

PII cache[N]; int len = 0;

ll Sum;
int Find_Root(int u) {
	for (PII it : Sub[u]) {
		register int v = it.fir;
		if (sum[v] * 2 > Sum) {
			register int pos; ll sumu;
			for(pos = it.sec, sumu = Sum - sum[v]; pos != from[u]; pos = from[pos])
				sum[pos] += sumu, cache[++ len] = mp(pos, sumu);
			return Find_Root(v);
		}
	}
	return u;
}

int bas;
inline ll Query() {
	register int pos = Find_Root(bas);
	For (i, 1, len) sum[cache[i].fir] -= cache[i].sec; len = 0;

	ll res = tot[pos];
	for (register int u = from[pos], Last = pos, dep = 0; u; u = from[Last = u], ++ dep)
		res += tot[u] - tot_fa[Last] + (sum[u] - sum[Last]) * dis[pos][dep];

	return res;
}

signed main () {

	File();

	int n = read(), q = read();
	For (i, 1, n - 1) {
		int u = read(), v = read(), w = read(); Add(u, v, w);
	}

	maxsz[rt = 0] = nodesum = n; Get_Root(1); Dfs_Div(bas = rt);
	For (i, 1, n) if(cur[i]) reverse(dis[i], dis[i] + cur[i]);

	while (q --) {
		int pos = read(), uv = read();
		Sum += uv; Update(pos, uv);
		printf ("%lld\n", Query());
	}

	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

unity的UGUI之中锚点(Anchors)和中心点(Pivot)、Shift和Alt键功能

在UGUI的控件属性之中,最上方的Rect Transform一栏可以看到锚点和中心点: 锚点Anchors 控件用于定位自身的基准点 可以点击左上角的方框,在其中选择锚点的不同方式: 注意图中,黄色的小点...

路过暴风
51分钟前
7
0
如何将div放置在其容器的底部? - How can I position my div at the bottom of its container?

问题: Given the following HTML: 鉴于以下HTML: <div id="container"> <!-- Other elements here --> <div id="copyright"> Copyright Foo web designs </div> </div> I would like #cop......

富含淀粉
今天
10
0
Distinct()与lambda? - Distinct() with lambda?

问题: Right, so I have an enumerable and wish to get distinct values from it. 是的,所以我有一个可枚举的,并希望从中获得不同的值。 Using System.Linq , there's of course an ext......

法国红酒甜
今天
16
0
学习编写编译器[关闭] - Learning to write a compiler [closed]

问题: Preferred languages : C/C++, Java, and Ruby. 首选语言 :C / C ++,Java和Ruby。 I am looking for some helpful books/tutorials on how to write your own compiler simply for......

技术盛宴
今天
17
0
OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
今天
48
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部