【CSP-S2019】D2T3 树的重心

CSP-S2019 D2T3 树的重心

题目

题目描述

小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：

1. 一个大小为 $n$ 的树由 $n$ 个结点与 $n?1$ 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。
2. 对于一个大小为 $n$ 的树与任意一个树中结点 $c$，称 $c$ 是该树的重心当且仅当在树中删去 $c$ 及与它关联的边后，分裂出的所有子树的大小均不超过 $?\frac{n}{2}?$（其中 $?x?$ 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 $1$ 或 $2$ 个。

课后老师给出了一个大小为 $n$ 的树 $S$，树中结点从 $1?n$ 编号。小简单的课后作业是求出 $S$ 单独删去每条边后，分裂出的两个子树的重心编号和之和。即：

$$\sum _{(u,v)\in E}?\sum _{\genfrac{}{}{0ex}{}{1\le x\le n}{且x号点是S_u^{\prime }的重心}}x+\sum _{\genfrac{}{}{0ex}{}{1\le y\le n}{且y号点是S_v^{\prime }的重心}}y?$$?

上式中，$E$ 表示树 $S$ 的边集，$(u,v)$ 表示一条连接 $u$ 号点和 $v$ 号点的边。$S_u^{\prime }$? 与 $S_v^{\prime }$? 分别表示树 $S$ 删去边 $(u,v)$ 后，$u$ 号点与 $v$ 号点所在的被分裂出的子树。

小简单觉得作业并不简单，只好向你求助，请你教教他。

分析

40 分的做法是枚举一条边，将它断掉后再暴力求出两边的重心。

结论： 重心必须在以根节点为起点的重链上。

证明： 不会。。。

然后我们可以利用这个结论，枚举每一个点，统计每个点在删掉边后对答案的贡献次数即可。

当我们分裂出一棵完整的子树时，就像这样：

对于以 $v$ 为根的子树的这部分，根据结论，我们沿着以 $v$ 为起点的重链往下跳就可以了。

对于剩余的部分，我们考虑换根。将剩余的部分提成以 $u$ 为根的树，然后暴力修改重儿子和重链即可。

我们可以用倍增来优化寻找重心的这一部分。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;const int Maxn = 300000;
const int Maxlog = 19;
typedef long long ll;#ifdef LOACL
bool ___;
#endifstruct Edge {
    int to;Edge *nxt;
};
Edge pool[Maxn * 2 + 5];
Edge *G[Maxn + 5], *ecnt;
inline void addedge(int u, int v) {
    Edge *p = ++ecnt;p->to = v, p->nxt = G[u];G[u] = p;
}int N;
int siz[Maxn + 5];
int mxson[Maxn + 5], mx2son[Maxn + 5];
ll ans;int s[Maxn + 1][Maxlog + 2];
int f[Maxn + 5];inline void clear() {
    for(int i = 1; i <= N; i++)mxson[i] = mx2son[i] = 0;for(int i = 1; i <= N; i++)for(int j = 0; j <= Maxlog; j++)s[i][j] = 0;for(int i = 1; i <= N; i++)G[i] = NULL;ecnt = &pool[0];ans = 0;
}
inline void modify(int u) {
    for(int i = 1; i <= Maxlog; i++)s[u][i] = s[s[u][i - 1]][i - 1];
}
void PreDFS(int u, int fa) {
    siz[u] = 1, f[u] = fa;for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(v == fa) continue;PreDFS(v, u);siz[u] += siz[v];if(siz[v] > siz[mxson[u]]) {
    mx2son[u] = mxson[u];mxson[u] = v;} else if(siz[v] > siz[mx2son[u]])mx2son[u] = v;}s[u][0] = mxson[u];modify(u);
}
inline void calc(int u) {
    int tot = siz[u], rt = u;for(int i = Maxlog; i >= 0; i--)if(tot - siz[s[u][i]] <= tot / 2)u = s[u][i];if(siz[s[u][0]] <= tot / 2) ans += u;if(u != rt && siz[u] <= tot / 2) ans += f[u];
}
void DFS(int u, int fa) {
    if(fa != 0) calc(fa), calc(u);int flag = 0, t1;if(N - siz[u] > siz[mxson[u]]) {
    t1 = mx2son[u], flag = 1;mx2son[u] = mxson[u], mxson[u] = fa;} else if(N - siz[u] > siz[mx2son[u]]){
    t1 = mx2son[u], flag = 2;mx2son[u] = fa;}for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(v == fa) continue;siz[u] += siz[fa] - siz[v], f[u] = v;if(v == mxson[u]) s[u][0] = mx2son[u];else s[u][0] = mxson[u];modify(u);DFS(v, u);siz[u] -= siz[fa] - siz[v], f[u] = fa;}if(flag == 1) {
    mxson[u] = mx2son[u], mx2son[u] = t1;} else if(flag == 2) mx2son[u] = t1;s[u][0] = mxson[u];modify(u);
}#ifdef LOACL
bool ____;
#endifint main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint _;scanf("%d", &_);while(_--) {
    scanf("%d", &N);clear();for(int i = 1; i < N; i++) {
    int u, v;scanf("%d %d", &u, &v);addedge(u, v), addedge(v, u);}PreDFS(1, 0);DFS(1, 0);printf("%lld\n", ans);}
#ifdef LOACLprintf("%.2f\n", (&____ - &___) / 1048576.0);
#endifreturn 0;
}