NGC5457's Site

分类： OI

  • 求一棵树任意子树的重心

    （2022.11.21 重写）

    定义

    设 $\newcommand\siz{\operatorname{siz}}\newcommand\hson{\operatorname{hson}}\siz(x)$ 表示 $x$ 的子树大小（含 $x$），$\hson(x)$ 表示 $x$ 的重儿子。将边 $(x,\hson(x))$ 称为一条重边，其余不满足该条件的边称为轻边；将相邻的重边两两相连形成的链称为重链。

    命题

    一棵以 $\newcommand\rt{\text{rt}}\rt$ 为根的树，其重心 $c$ 满足以下条件：

    • $c$ 在以 $\rt$ 为顶的重链上；$(1)$
    • $c$ 的所有祖先（记其中一个为 $x$），均满足 $\siz(\hson(x))>\frac{\siz(rt)}{2}$；$(2)$
    • $\siz(\hson(c))\leq \frac{\siz(rt)}{2}$。$(3)$

    （更多…）

  • 洛谷题库 P2272 [ZJOI2007]最大半连通子图 题解与思路重现

    洛谷题库 P2272 [ZJOI2007]最大半连通子图

    有感而发，今晚一定先写篇题解。这可是我AC的第一道紫题！

    题目中说半连通子图指的是对于图$G(V, E)$，$\forall u, v \in V$ 有 $u \to v$ 或者 $v \to u$。当时我对于“或”的理解是异或，也就是二者不能同时存在。

    ——那这题基本没法做啊？比如我们作一次DFS，搜索的时候光是找到一条横叉边，就已经让人头疼怎么处理；更别说还要判环，还要找“最大”的半连通子图。

    但有一点是可以确定的——当图中可以将环处理掉时，“半连通子图”将会是一条链。易知对于链上的节点$u, v$ (u是v的祖先)，都有$u \to v$。

    （更多…）