今天摆烂了！
上午终于有正常的模拟赛了，正常的 OI 赛制，正常的没有 subtask，正常的部分分，爽！???
上来 T1 一眼秒了?。T2 划拉了半天找不到性质写暴力跑了，T3 发现是下凸壳，不会三分所以二分的斜率，卡了卡常过了?。T4 想了半天长剖发现可以直接换根，大常数 \(nlogn\) 做法写出来没测 \(1e6\) 数据跑路了，惨丢 50pts?。
又打了下 T2 的表发现相对位置不变，又搞了搞就出来式子了。最后写出来了，但是没取模，\(100pts\rightarrow 30pts\)。???
最后 \(100+30+100+50=280\)，喜提 rk2。
喜报：OP 解封了。
晚上去搬 whk 的书了。yy 对 sbf 说：头发长的我都认不出来你了。
重温yjj经典（？）
crimson000 16:44:01
有人地理学考没A吗
sbf 16:44:37
我
haosen 16:45:46
@sbf 你tm不是全A？
mjsdnz 16:45:58
sbf是全A
mjsdnz 16:46:08
sbf有B吗？
crimson000 16:46:25
sbf没B
bingxin 16:46:32
sbf没B
newamnesia 16:46:37
sbf没B
crimson000 16:48:25
6
crimson000 16:48:35
sbf没B
经典再现
crimson000 在写一种中点随机选取的很新的线段树。
crimson000：妈的，这死吗 MLE。
Tibrella：你怎么说“妈的”不说“爸的”，郭楠真恶心，下头男把封建残余当成国宝了是吧
crimson000：妈的这死爸MLE
Tibrella：怎么光说死爸不说死妈，这个世界上只有男的没有女的？女性不配放到你的语言里面？也对，你不配说女性，郭楠真恶心
crimson000：这死全家的MLE
Tibrella：怎么光说全家不指出来有女性？不知道女性优先吗？还是说女性不配有姓名？
推歌：迷える音色は恋の唄 -からとPanchii少年 feat.はるの
有人推了另一首群愿的曲子所以我也推一首（
今天模拟赛 T4
首先我们可以发现两条路径的合并方法就是相乘，因为 \(2^{d_{u, x}}\times 2^{d_{x, v}}=2^{d_{u, v}}\)。因此可以每个点存储和它相关的路径的权值和。
我们进行一个分类讨论。
- 当 \(lca(u, v)\) 不为 \(u, v\) 时，路径的数量就是两边子树的大小。设 \(f_u\) 为 \(u\) 子树内所有点到 \(u\) 这些路径的权值和。根据我们上边的结论，我们可以得到答案为：\(f_u\times 2^{dist_{u, v}}\times f_v\)。
- 当 \(lca(u, v)\) 为 \(u\) 时（\(v\) 同理），我们可以和上面一样，设 \(g_u\) 为刨掉 \(u\) 子树之后剩下的所有点到 \(u\) 的路径的权值和，我们设 \(v\) 的第 \(dep_v-dep_u-1\) 级祖先为 \(v'\)（也就是 \(u\) 的直属儿子），那么答案为 \((g_u+f_u-f_{v'}\times 2-1)\times 2^{dist_{u, v}}\times f_v\)，里面有个 \(-1\) 的原因是我们在 \(f\) 和 \(g\) 中都计算了一遍 \(u\to u\) 这条路径。
现在就考虑如何求出 \(f\) 和 \(g\)，这个可以通过树形 dp 求出。转移如下（设 \(u\) 为父亲，\(v\) 为儿子）：
时间复杂度应该是可以做到在线和离线都能 \(O(n)\)，但是我不会 \(O(n)\sim O(1)\) 求 \(k\) 级祖先。
今日图图：
