2024/10/17

今天还有一道题没做，等以后有时间再来补。

abc187E Through Path

每次修改的两个点之间有一条连边，对于每次 \(1\) 修改：

• 若 \(b\) 是 \(a\) 的父亲，只需要将 \(a\) 子树加 \(x\)。
• 若 \(a\) 是 \(b\) 的父亲，只需要全局加 \(x\)，将 \(b\) 子树减 \(x\)。

HNOI 2018 省队集训 Day 5 Party

边是单向边，有要求距离尽量短，所以集合点一定是再 LCA 上。

我们可以先通过树剖 + bitset 先将每个人到 LCA 上拥有那些特产，之后将每个人与特产连边，然后来一次二分图匹配。

但这样子时间复杂度太高了，但我们知道 Hall 定理，也就是说，我们只需要枚举人的所有子集，答案就为 \(\min\frac{sum}{cnt}c\)，其中 \(sum\) 表示特产种类数，\(cnt\) 表示子集大小。

时间复杂度 \(O(\frac{q\log n+2^cc}{w})\)。

ZJOI2018 胖

显然，最开始增广肯定是从要修建道路的点开始，之后的每次增广都是从这些点向相邻点拓展。

也就是说，我们只需要求出每个要修建道路的点能够拓展的区间 \([l_i,r_i]\)，最后的答案就是 \(\sum r_i-l_i+1\)。

如果能够从一个点 \(x\) 拓展到点 \(y(y\le x)\)，那么需要满足 \([y-(x-y),x]\) 中不存在一个点到 \(y\) 的距离更短。

可以将区间拆为 \([y-(x-y),y]\) 和 \([y+1,x]\) 来处理。

右端点同理，需要注意距离相同的情况。

CTT2020 基础图论练习题

由兰道定理得，竞赛图中得强连通分量个数为 \(\sum_{i=1}^{n}[\sum_{j=1}^i out_j=\frac{i(i-1)}{2}]\)，其中 \(out\) 表示每个点的出度。

不妨让我们来枚举翻转得边是哪一条，反转过后强连通分量个数可以 \(O(1)\) 求出。