题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单，给你一张图，然后图中不能选最大相邻点，最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目，但是显然，这，并不是一棵树

根据题目可得，每一个人只会有一条出边，即，这张图中，一张节点个数为 $n$ 的联通块，会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边，删掉后就是树了

设这条边为 $u - v$ 的边，则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ，当反向边即可

题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323

我看到题目的一瞬间

我是在学 oi 还是在学物理？

然后我仔细思考了一下，这两个镜子来回反射，您这是要求极限？

然后我仔细思考了一下

设 $f_i$ 为从 $1$ 到 $i$ 的透光率，$g_i$ 为从 $i$ 到 $1$ 的反光率

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组

后缀数组用于解决各种玄学字符串问题，准确来说，它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

• 倍增法 (本博客所讲述) -- $O(n \log(n))$
• DC3 -- $O(n)$
  • DC3 虽然从复杂度分析的角度而言比倍增快，但配合各种常数问题，在信息学竞赛中反而容易被卡……
• SA - IS 算法 -- $O(n)$
  • 可以参考这篇 Luogu 日报: https://www.luogu.org/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa

因为我太菜了，所以我就讲倍增求法

题目链接: https://www.luogu.org/problemnew/show/P3174

这应该是我第一次没看 sol 做紫题吧……

虽然个人感觉比大多数紫题简单许多

题目本质是要求最长链的，但是要求是带每个点周围点的

我们设每个点的点权是这个点的连接点个数减 1

然后求最长链

得出来的链的长度 +2 即为答案

可以理解为因为大多数点都有一条边要连出去防止重复计算而减一

但是这样链头链尾会没算上，所以加二

Day -1

上午起来收拾了一下就前往乌鲁木齐市机场了

在机场里面互相定位是一件困难的事情，我们最终通过奇迹淫巧和瞎挥手聚在了一起

然后是漫长的安检和候机....

在经历各种各样奇怪的娱乐过后，飞机终于落地

飞机上拍的云朵

下去坐地铁，站了一个多小时后有疯狂转圈终于吃上了人生中第一顿麦当劳并到达了宾馆

发现电视有 HDML 口，接之

一顿瞎嗨，用电视看了看鬼畜和老番