首页 > 其他分享 >题解 P2726 【[SHOI2005]树的双中心】

题解 P2726 【[SHOI2005]树的双中心】

时间:2024-10-01 23:44:58浏览次数:6  
标签:ver int 题解 pos sze P2726 Maxn SHOI2005 son

首先,我们会有一个很简单的想法,枚举断边,产生两棵子树,然后在两棵树内分别求带权重心,计算贡献,这样的话复杂度是 \(O(n^2)\) 的。

那么我们要好好利用 $h \leq 100 $ 的性质。

考虑 \(sze[u]\) 为带权重量,\(g[u]\) 为以 \(u\) 为根的树,所有点都到 \(u\) 的代价。

所以 \(g[u] = \sum\limits_{v\in{son(u)}}{g[v] + sze[v]}\)

考虑 \(f[u]\) 为 \(u\) 在的一棵树中,所有点到 \(u\) 的总代价。

由于计算是动态的,我们考虑转移。

对于 \(v \in son(u)\) 有 \(f[v] = f[u] + (S - sze[v]) - sze[v]\)

如果 \(v\) 比 \(u\) 更优,当且仅当 \(2 * sze[v] > S\)

我们发现,只有两个候选项,重儿子和次重儿子。递归时顺带维护变化即可。

最坏情况可能会是一条到底的链,所以复杂度 \(O(nh)\)

code:

const int Maxn = 5e5 + 5, Maxm = 1e6 + 5;
int n, cnt = 0, w[Maxn], head[Maxn], ver[Maxm], nxt[Maxm];
inline void AddEdge(int u, int v) {
	ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
	ver[++cnt] = u, nxt[cnt] = head[v], head[v] = cnt;
}

int dep[Maxn], fat[Maxn], son[Maxn], son2[Maxn];
int sze[Maxn], g[Maxn], cut, ans = INT_MAX;
inline void DfsFir(int u) {
	sze[u] = w[u];
	for (int i = head[u]; i; i = nxt[i]) {
		if (ver[i] == fat[u]) continue;
		dep[ver[i]] = dep[u] + 1; fat[ver[i]] = u;
		DfsFir(ver[i]); sze[u] += sze[ver[i]];
		g[u] += g[ver[i]] + sze[ver[i]];
		if (sze[ver[i]] > sze[son[u]]) son2[u] = son[u], son[u] = ver[i];
		else if (sze[ver[i]] > sze[son2[u]]) son2[u] = ver[i];
	}
}

inline void getans(int u, int val, int all, int &ret) {
	chkmin(ret, val); int v = son[u];
	if (v == cut || sze[son[u]] < sze[son2[u]]) v = son2[u];
	if (!v) return;
	if (2 * sze[v] > all) getans(v, val + all - 2 * sze[v], all, ret);
}

inline void DfsSec(int u) {
	for (int i = head[u]; i; i = nxt[i]) {
		if (ver[i] == fat[u]) continue;
		cut = ver[i]; int x = INT_MAX, y = INT_MAX;
		for (int pos = u; pos; pos = fat[pos]) sze[pos] -= sze[ver[i]];
		getans(1, g[1] - g[ver[i]] - dep[ver[i]] * sze[ver[i]], sze[1], x);
		getans(ver[i], g[ver[i]], sze[ver[i]], y); chkmin(ans, x + y);
		for (int pos = u; pos; pos = fat[pos]) sze[pos] += sze[ver[i]];
		DfsSec(ver[i]);
	}
}

signed main(void) {
//	file("");
	read(n);
	for (int i = 1, u, v; i < n; i++)
		read(u), read(v), AddEdge(u, v);
	for (int i = 1; i <= n; i++) read(w[i]);
	DfsFir(1); DfsSec(1); writeln(ans);
//	fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

标签:ver,int,题解,pos,sze,P2726,Maxn,SHOI2005,son
From: https://www.cnblogs.com/EternalEpic/p/18444281

相关文章

  • AT_abc373_e 的题解
    (一)二分套二分。(感觉是一个很麻烦的做法。)题目问的是让额外给的票最少,考虑二分答案。设二分的答案为\(x\),该候选人原来的得票为\(v\),想要超过他至少要\(x+v+1\)。同时用前缀和维护区间和。第一种情况为该候选人在前\(m\)个人中,如下图所示。绿色箭头为被讨论的人,蓝色箭......
  • 优美函数 题解
    题意简述给你函数\(f\):\[f(x,y,u)=\left\{\begin{array}{rcl}u-y,&x=1\\u,&1<x\ley,\\gcd(x,y)=1\\-x\cdoty,&x\neq1,\\gcd(x,y)=x\\0,&\text{otherwise}.\end{array}\right.\]对于一个长度为\(n\)的序列......
  • ABC 模拟赛 | A Passing Contest 001题解记录(A,B,C,D)
    比赛链接https://www.luogu.com.cn/contest/126344[APC001]A-CT不必多说,多次取模#include<iostream>#include<algorithm>#include<string>#include<string.h>#include<queue>#include<deque>#include<math.h>#include<map>......
  • CF1214G Feeling Good 题解
    题目链接点击打开链接题目解法我真菜啊,感觉每一步都不难,但一步都没想到/yun考虑两行\(x,y\)什么时候可以构造出合法的矩形?即\(x\)中需要有\(y\)对应位置为\(0\)的\(1\),\(y\)中需要有\(x\)对应位置为\(0\)的\(1\)归纳一下,\(x\)不是\(y\)的子集且\(y\)不......
  • CF2018E2 Complex Segments (Hard Version) 题解
    题目描述\(T\)组数据,给定\(n\)条线段\([l_i,r_i]\),称一个线段集合是复杂的,当且仅当:它可以被划分成若干个大小相等的线段组。两条线段相交当且仅当它们在同一组。求用这\(n\)条线段构成的复杂线段集合的最大值。数据范围\(1\len,\sumn\le3\cdot10^5\)。\(1\l......
  • CF280C Game on Tree题解
    题目描述给定一棵有根树,结点编号从1到n。根结点为1号结点。对于每一次操作,等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后游戏结束。也就是说,删除1号结点后游戏即结束。要求求出删除所有结点的期望操作次数。不是哥们,我好不容易国庆......
  • 题解:AtCoder Beginner Contest AT_abc373_d ABC373D Hidden Weights(格式美化版)
    题目传送门题目翻译给你一个NNN个点,MMM条边的有向图,其中边有边......
  • CF429E Points and Segments 题解
    题目链接点击打开链接题目解法真难啊/yun把区间染成红色看作区间\(+1\),染成蓝色看作区间\(-1\),要求是每个点上的数\(\in\{-1,0,1\}\)可以选择的数有\(-1,1\)不太好做,我们考虑将限制变成每个点上的数只能为\(0\)我们记经过点\(x\)的线段数量为\(cnt_x\)如果\(cnt......
  • 题解:P11075 不等关系 加强版
    这是洛谷转移过来的题解,作者是4041nofoundGeoge(我自己,记得关注呀)题目大意对于一个字符串s1,s......
  • [HNOI2010] 城市建设 题解
    题意给定一个图,每次修改一条边的边权,每次修改后输出该图的最小生成树边权和,询问间不独立。思路在线不好做,考虑离线下来,可以使用线段树分治。我们称在当前区间\(\left[l,r\right]\)的边为动态边,不在的边为静态边。但这样每次遍历到叶子节点的时候静态边的数量都是\(m\)的......