20220920总结

某场考试T1

怎么说，题不难，但是需要想一下。

考虑右端点进行贪心的思路挺妙的。

某场考试T2

比较套路的题，先弄出一个 \(t\times n^4\) 的凑合做，然后发现两维转移系数独立，转移答案为三角形和形式乘上两维系数，可以考虑固定第二维，单独计算第一维不同转移系数对应的式子，每一种系数的变化量为 \(O(1)\)，所以一次转移可以做到 \(O(n)\)。

某场考试T3

神仙题，考场上猜到树一定有解，但是想的是通过背包来构造解，事实上，可以归纳的证明每棵子树带来的差异可以取 \([-sz_u,sz_u]\) 中的任意值，所以对于树暴力构造一条从根到某个点的路径，可以满足路径两边大小相等。

考虑图上的结果。

09 年的一篇集训队论文告诉我们对于图上的问题，往往可以考虑其生成树的解法，从而进行拓展，发现无向图的生成树没有横插边，所以直接选取生成树上的答案，由于没有返祖边，所以原来合法的同样合法。

某场考试T4

也是比较套路的题。

很明显本质上是给你个一次函数做路径边权，然后 \(k\) 的值为 \(1\)，所以计算出每个点每个 \(k\) 的值即可。

我选择分层图跑 \(dij\) 外加大力卡常，但这是一种非常 \(SB\) 的行为，\(dij\) 本质上还是保证了转移的无环性，但 \(TM\) 这个转移本来就无环还跑你大爷的 \(dij\)，暴力 \(dp\) 出来做凸包就行。

然后从 \(n\) 的各个在凸包上的 \(k\)，倒推回去看那些点可能被用到，倒推可以写成记搜，这样只用存一遍边。