10.18 闲话

本来没有写闲话的打算的，但是大家都在写闲话，而且我这个博客已经八百年没更新了，所以我决定瞎写点水一水，顺便展示一下 S2 OieR 良好的精神风貌和健康的精神状态。

日记

我是傻逼。

上午不想写题，给自己博客文章都加了分类（之前一直忘了）。

为什么课间没有人 tankard 启动？

喵了一眼明天安排，发现我明天上午有 ZR，下午还有 CSP 全假模拟，累了，毁灭吧。

快中午的时候头疼加眼睛疼，就差性子疼了，也好，提醒我下午给自己小小放个假。

睡了一下午，什么也不想做，忽然觉得自己是不是太颓废了，于是起床打开了 Visual Studio Code，但是不知道为啥就跳转到 B 站了，一定是电脑搞的鬼。

晚上听着歌打了打各种板子，还是没写题，打完就删，接着打下一个，什么记录也没留，挺好。

感觉越临近考试越是有一种内耗感，好在自己还是能意识到这种感觉，并且给予调节。

啊，明天要面对双重打击了，早点睡了。

我推の歌

“在机房不要戴着耳机听歌”

但我回家了，欸嘿。

WATER ——A39

一曲很不错的电音，虽然许多人认识这首音乐是靠音游，但抛开音游，其独特的曲调和强烈的节奏也值得单曲循环。

Gone Angles ——Mili

带刀神曲（你知道的太多了），婉转凄凉，但主唱声线平静温和，Mili 的音乐常给人一种黑童话的感觉，搭配一个凄美的故事食用效果更佳。

口胡式题解

P3629 巡逻

要求在树上加一到两条边使得从 1 号点遍历所有点并回到 1 号点的路程最短，加的边必须被且只被经过一次。

首先是一条边都不加的时候，这是遍历一遍需要把所有边经过两遍（正向一遍，反向一遍），所以初始答案 $ans=2\times(n-1)$。

接着考虑只加一条边，这一条边会与其他若干边成环，环上的边只用被经过一次，因为从环上某点绕环一周可以回到该点，不会有“回溯”。环上边的数量等于选中两点间边的数量加一，也就是说选中两点 $i,j$，对答案的贡献是 $1-dis(i,j)$。要使贡献绝对值更大，即要使 $dis(i,j)$ 最大，而树上距离最远的两点即为直径两个端点，所以找到直径即可。

之后考虑加入第二条边，第二条边会再成一个环，此时环上的边有两种可能：原来不在环上和原来在第一个环上。因为新加边必须被经过一次，又因为两条新加边不共环，所以两个环都要被遍历一遍，则原来在第一个环上的边会回退贡献，而原来不在环上的边可以被少走一遍。于是再选中两点 $i,j$，设 $i,j$ 路径上有 $num$ 条边在第一个环，则选 $i,j$ 对答案的贡献为 $1-(dis(i,j)-num)+num$，于是可以将原来在环上边的边权设为 $-1$，再找一遍直径即可。在这里，直径的意义由最长路径扩展到最大贡献。

做法上推荐使用树形 DP，第二次跑直径的时候别忘了初始化负无穷。