noip 邮寄

挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂

day 0

写板子，但是写的不多。

写了个 lct，三个 NOI Ag（我，@jinqihao2023，@DeepSkyCore）调了一个小时没调出来，怎么一回事呢？

晚上放，完全开摆。

day 1

没有雀，不会挂分（

进考场，开题，看 t1，写了个贪心挂了，然后之后的 20 分钟一直在重复 想贪心，写贪心 的过程，然后一直没过大样例，心态完全爆炸，选择启动 t2。

t2 发现直接确定能知道的点，然后两点之间可以直接算出来方案数，两边也能算，然后就没了。写了下 15min。

开 t3，先反过来建圆方树，发现非常像一道叫 黑色半径 的题目，然后先算只有一个根的情况，然后减去两个根共同算重的情况，然后根据点边容斥这东西已经容斥完了，直接写一下就行了，算两个根的情况可以直接 dfs 记录子树内的所有能贡献点的途径度数的乘积的逆元。

开 t4 前先开 t1，发现了一个更加正确的贪心，浅浅的证明了一下发现对完了，这下 t3 < t1 了（

开 t4，首先根据经典结论 dep_{\operatorname{lca}_{l\leq i\leq r}(i)}=\min_{l\leq i<r}dep_{\operatorname{lca}(i,i+1)}，直接先求出来所有的相邻 lca 的 dep，然后哦这题就跟树没关系了（，然后考虑建出笛卡尔树，那么所有能做出真正贡献的的区间只有 O(n)！然后题目就变成了，你有若干个带权区间，有若干带权询问，如果能找到一个长度为 k 的区间，使得其被询问与区间同时包含，那么你就能获得区间权值的贡献，最后求贡献 max。

然后考虑到当询问不包含区间的时候是容易解决的，可以直接二维偏序。考虑询问包含区间那它就是三维偏序了！！！！！！！！！！！！！！！！！！！

我先别急，由于区间都是笛卡尔树上的，因此我们扫描区间长度，当笛卡尔树上一个区间的长度还大于当前扫描的长度时，其祖先的区间是没有必要加入的！！因此所有区间都互相不交了，三维偏序直接变二维偏序了！！！！！！！！！！！！！！

然后画 1h 写了下，花 0.5h 卡了下常，还剩 2h，怎么 noip < csp 的啊？

出考场发现好像大家都直接写的三维偏序，但是都跑的飞快啊？？？？？？那我不是小丑了？？？？？？

然后战术开摆，后面忘了。

day ?

赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢赢