赛时
开 T1，发现立即有了 \(O(n^2)\) 的思路，能有 \(45\) 分，但是先不急，看看后面的题。
T2、T3、T4 似乎都可以写个暴力。
又想了想，T1 还需要求出个 LCA，所以复杂度是 \(O(n^2\log n)\) 的，开写。
很快写完，调不过，边界很不好处理。直到 \(1.5\) h 才调出来 \(O(n^2\log n)\)。
上个厕所清醒一下，发现后面有一档链的 \(10\) pts 很好写，\(2 \min\) 写完。
再考虑 \(k=1\) 的情况，感觉树形 DP，先跳了。
T2 很像什么数据结构维护的题目，一眼 \(O(n^2)\) 的做法。
考虑了 \(L=R=\dfrac{n(n+1)}{2}\) 的分数，想到了 [AGC005B] Minimum Sum，会了个 \(O(n\log n)\) 处理区间左右端点的情况。
写完后大概 \(2.5\) h了，Sorato 早已经过掉 T1 和 T2，很难绷，又去想 T1，还是不会 \(k=1\)。
\(T3\) 很像错排问题，但是没有多想，直接写了个 \(O(n!)\) 的做法。
\(T4\) 发现做过类似题目，但是基本想不起来怎么做了，应该有个区间 DP 的部分分做法。
没时间想了，写了个 BFS 爆搜扔在那里。
最后 \(20 \min\) 再去想 \(k=1\) 的做法，会了以 \(1\) 为根的树形 DP，但是不会换根，很寄。（此时的 T1 已经很接近正解了）。
结束。估分：\(55+20+5+10=90\)。
赛后
得分：\(55+20+5+10=90\)。
膜拜 changziliang konglingzhao Sorato Heldivis
一分未挂，但是排名很低，感觉最近的状态很不好。
很多同学都挂分了，唉，这就是 OI 赛制。
讲题。
T1 随便 \(O(n)\) 树形 DP 就能过了，wssb，这么简单做法想不出来。
T2 二分这个我也想到了，但是不太会 check，看来要加训二分了。
T3 正解就是容斥，还用到了环上 k 元独立集计数，很厉害的题。
T4 找找规律就可以了，寄。
题解
咕了。
标签：10,20,log,T2,Day,T1,2024,CSP,DP From： https://www.cnblogs.com/zhujiangyuan/p/18438296/dmy2024_6