NOIP 2025游记

· · 生活·游记

T1，大概5min会了。

T2，大概猜了个结论，试着举了一下反例，发现找不到，实现上感觉随便 \Theta(n^2)，但是数据范围比较神秘，先跳了。

看T3,T4，不是T4怎么又是数据结构/fn，感觉T3不可做，于是想了好久T4，应该只发现了对于固定长度可以单调队列，快 2h 的时候没有想到任何可能的做法。此时有一点慌，于是转T3，又苦磕了0.5h，发现对于一个子树，知道mex之后可以不用填 >mex 的数，留到之后再填，于是一个子树内的信息可以表示成 x,y 表示 mex 和剩余自由点数量，转移就先将 u 的值设为子节点 mex 最大值，然后累加自由点数量，最后可以用若干个自由点来使 mex 增大等量值。但是这个神秘东西好像只能 \Theta(n^3)，和 m 不太有关系 /kk。

此时感觉自己非常失败，于是花了 0.5h 打了一下前两题，T2 跑得还挺快，就没管。接下来冷静了一下重新刻画问题，发现可以变成选择一种树链剖分，然后每个点 u 的权值是从 u 往上最长链长度，最大化所有点权值和，这个就可以随便 nm^2 DP了，此时还剩 1.5h，赛场心态比较奇怪，一直在 冲T3 和 试图打T4更高分中徘徊，感觉浪费了很多时间，最终在浪费 0.5h 后决定放弃 T3了，最后用 1h 打了 T4 45 分。

估分 100+100+76+45=321。

出分 100+100+68+45=313。

至于为什么挂分：