今天上午模拟赛，被暴打喽。
上来刚了一个小时 T1，没想到时光倒流，感觉像个大分讨?，开摆拿 vector 艹 50 分外加 \(m=1\) 分讨混 60pts 跑路???。T2 想了 20 分钟依旧想不到正解，直接开摆枚举断哪条边然后 dfs 跑路，T3 上来想到了弱智 30pts 做法，最后 40 分钟想到了弱智 50pts 做法还写挂 10 分真的绝了?。T4 一眼不可做，但一眼费用流暴力就有 34pts，调了 40 分钟没调出来费用流，最后发现的问题：
e[idx] = b, ne[idx] = h[a], ....
// 反向边
e[idx] = a, ne[idx] = h[a], h[a] = idx ++;
反向边连到 \(a\) 上（大嘘）
最终得分：\(60+46+40+34=180\)。
摆喽。
今天下午又离线了，zzz 讲构造，中午也没睡觉，下午又饿脑子又疼，开摆了。
下午看到朵龙_耳在 P lyt 的图，链接我就放下面了：here。
明天讲课老师 19:57:14
想问问大家对DP的一些比较经典的优化思路掌握如何？/kel比如说DP+树上问题可能遇到的套路（dsu on tree、长链剖分、点分治点分树、线段树合并 / 启发式合并、线段树合并维护函数值、动态DP 、LCT、dfs序应用，我看有学长讲这个板块）；对于序列和时间的DP：斜率优化 / 决策单调性 / 凸优化；对于状态复杂一些的状压DP、数位DP；对于概率期望、计数DP，大家有感觉哪些是比较薄弱的地方吗，我可以多准备一些内容
crimson000 19:59:25
啥都不会/kel
李bingxin 19:59:27
啥是比较薄弱啊/yiw 我咋一个都不会
ikura 19:59:27
凸优化不会/kel
Tibrella 20:00:19
啥都不会
以及趣图：
一直没推过音游曲，这次推个音游曲。
推歌：Defection -TeddyLoid
作为某英国无良小作坊的音游 4.0 版本的第一首曲子，也是 FV 曲包唯一一首没有 PV 的曲子，却也是挺好听的，个人感觉和后面的隐藏曲不相上下。
还有曲师是听完竹取飞翔写的这歌吗
P7165
不算特别难的题，只是我场上没想出来。
我们依旧考虑枚举断边，现在的目标就是寻找被分出去的部分的边分治重心。根据数学直觉，这条边一定会把这部分分成两个大小接近的部分。假设我们断的的 \(u\) 和它的父亲这条边，那么外面那部分分出去的 \(siz\) 就应该接近 \(\frac{n-siz}{2}\)。
我们就开始分类讨论。
- 如果第二条切的边在 \(u\) 到根的链上，那么我们要找的就是 \(siz_x - siz_u\) 最接近 \(\frac{n-siz}{2}\) 的点。
- 如果不在这条链上，那么我们就要找 \(siz_x\) 最接近的点。
这个最接近直接可以用 set 做，而对于如何维护 set 中的元素，我们可以在 dfs 到一个点时把它加入到 \(s_2\) 这个集合里，表示它在 \(u\) 到根的链上。而在退出时把它从 \(s_2\) 中删去，加入到 \(s_1\)，也就是上面讨论的第二种情况。
这样每次查 4 次前驱后继即可。
没拍到合适的恋恋 fumo 的图，还差点被恋恋刀了，放张之前找到的 fumo 图吧。
而且本来尝试把 lyt P 成恋恋的结果被恋恋看到了差dia