日记

15岁了。

Dynamic Shortest Path# Link to

发现 $\Delta w = w + dis_u - dis_v$。我们整一个新图，图中的边权就是 $w + dis_u - dis_v$。（$dis$ 还是原图里的最短路）然后跑出来最短路 $add_u$，可以发现 $dis_u \gets dis_u + add_u$。

那这有什么性质呢？我们发现由于至多把 $c$ 条边的边权 $+1$，所以最短路至多加 $c$，也就是说 $add_u \in [0,c]$。我们可以扔掉 dijkstra 的堆，改用一个桶，dijkstra 的复杂度就降成了 $O(n + m)$，总复杂度 $O((n + m)(\log n + q))$。

Nezzar and Hidden Permutations# Link to

先把度数为 $n - 1$ 的扔出去。

考虑在补图上做。考虑一个补图是菊花的图能否构造一个 $p,q$ 使得 $p_i \ne q_i$。这个图补图是一个菊花意味着：菊花的根和剩下的点都没有边，且剩下的点成环。我们可以这样构造：

• $p$：
  $p_{root} = 1$，剩下的环上的按照 $2 \sim n$ 依次赋值。
• $q$：
  $q_{root} = n$，剩下的环上的按照 $1 \sim n - 1$ 依次赋值。

这样我们就构造出来了。

考虑把补图的生成树整出来，然后把他分成几个菊花。因为在补图中加边等于在原图中删边，所以原图也一定合法。

整出菊花之后直接构造就是了。

后日谈 # Link to 后日谈

都 7 月下旬了我还那么菜

发现这事的时候我整个人都在抖