noip T3&T4

学术版

CarroT1212 @ 2024-11-30 15:12:02

目前进度是 T3 没想清楚 k=2，T4 赛后会 \log^2 的主席树实现二分套区间最大子段和。求此两题的后续处理思路。

可能我现在问有点急？但是确实一整个就挺破防的。

by HMZHMZHMZ @ 2024-11-30 15:16:52

k=2 考虑求出同时被两个起点达到的生成树。发现等价于起点连出去的边只有一条。

t4 考虑离线下来，合并 dep。就不需要主席树二分了。

by 幸存者 @ 2024-11-30 15:17:29

T3 k\le8 可以容斥，其他不会了

by 幸存者 @ 2024-11-30 15:17:58

https://www.luogu.com.cn/article/0k9e0r36

by Union_of_Britain @ 2024-11-30 15:39:52

@CarroT1212 无向图 dfs 树不能有横叉边，然后一个点的团那个完全图就是只能是一条链，链头是出发点或者连过来的点。把这个结构拼接起来就可以了。k=1 怎么 dp，设 h_i 为 i 从父亲下来的子树合法团选链方案数，这个直接先递推；设 f_i 为 i 算上连向父亲边，考虑子树的关键边，子树里面团选链的方案数，再设 g_i 为 f 和 h 交大小。然后转移去重就大概是考虑链头是这个儿子，链尾是前面的某个儿子减去掉就可以了，前缀和优化后为 O(n\log n)。

by ┭┮﹏┭┮ @ 2024-11-30 15:47:54

同求 T4 主席树思路，只会仨log

by Kazemaru @ 2024-11-30 15:50:48

T4 最大子段和常数太大了，要维护 4 个数，我们尝试改成维护每个位置和它后面第一个 0 的距离，询问的时候问 [l,r-k+1]。然后就大概率能卡过去了。

by Kazemaru @ 2024-11-30 15:51:57

然而我没写 fastIO 被击毙了。

by CarroT1212 @ 2024-11-30 15:58:57

@HMZHMZHMZ@幸存者@Union_of_Britain@Kazemaru 感谢大家抽出时间回复/ll

T3 大致理解了，算重的原理想不清楚根本做不了一点（

T4 可以细说一下吗

by 20_200 @ 2024-11-30 16:14:25

@CarroT1212 T3直接就是容斥，一堆点都可以作为根则他们都在一条链上，dp状态表示贡献之和，多一个点直接乘-1即可

by Kazemaru @ 2024-12-01 10:27:20

T3 的贡献等价于选出两个叶子，使得它们之间的路径经过某条给定的关键边，对应方案数是链上的 (deg-2)! 链外的 (deg-1)! 一起乘起来，注意 -1!=1。

枚举两个叶子就是 n^2，不会算重。

随便扫描线一下就可以。DP 也行。