炼石计划 10 月 28日 CSP-S 十连测 #5【补题】 - 比赛 - 梦熊联盟 (mna.wang)
复盘
T1 秒了。30min。
T2 题目越短越难。但是链的是经典题目，写了。小样例太水，大样例太大，不方便猜结论。于是先写暴力然后自己造样例。
模拟了五六组感觉可以按照 lca 的深度降序排序，然后能选就选。这个做法和链兼容。
但是需要维护树上路径加路径查 \(\max\)。树剖秒了。
三个做法融合起来的代码 5KB。调了 1e4514min 后树剖终于不挂了。
对拍。
T3 \(n \le 25\)？？好像一分不会啊。每条边都包含 "BJMP" 感觉好做，想。
但是 \(T \le 10^9\) 什么做法都过不了。放弃。
算了先写 \(n \le 5, T \le 10\) 的爆搜吧。写一半发现加个记忆化就是个 DP，复杂度 \(\mathcal O(16nT)\)，能过前两个部分分。
T4 \(n, k \le 15\) 爆搜过不去啊。好像又一分不会了。
我相信数据是很水的。于是写了爆搜加小剪枝。
预计 \(100+100+40+[0, 15] = [240,255]\)，实际 \(100+100+50+15=265\)。树剖没挂就是强。
总结
好的：
- 树链剖分没写挂。
- 没有挂分。
不足：
知识点
- T1：递推，矩阵加速；
- T2：贪心，树链剖分，LCA；
- T3：DP，矩阵加速；
- T4：
题解
A. 男女排队
显然有递推：
f[i][0] = f[i - 1][0] + f[i - 1][2];
f[i][1] = f[i - 1][0];
f[i][2] = f[i - 1][1] + f[i - 1][3];
f[i][3] = f[i - 1][1];
矩阵加速即可。
B. 树上最多不相交路径
模拟几组样例可以发现若按照 lca 的深度，从大到小，能选就选。具体需要树剖维护树上路径加，路径求 \(\max\)。
感性理解一下为什么这样是正确的。选择一条路径后，它的 lca 的子树中的点，是不能通过 lca 走到子树外面的。所以我们按照 lca 的深度降序选。
C. 生日
首先将一条 \(u \to v\) 的边拆成两条：\(u \to v\) 和 \(u \to\) 某个虚点 \(\to v\)，边权都是 \(1\)。分别表示不经过商店和经过商店。
中间这个虚点的数量可以做到 \(\mathcal O(n)\) 而不是 \(\mathcal O(m)\)。我们只需要把 \(u\) 的每条出边对应的虚点都设成 \(u' = u + n\) 即可。具体的，初始化 \(u \to u'\)，每次连边 \(u \to v\) 和 \(u' \to v\) 即可。
考虑一个弱化问题：从 \(1\) 出发，不对购买的商品进行限制，在 \(T\) 秒内回到 \(1\) 的方案数是多少。
显然 DP：设 \(f(u, t)\) 表示在 \(t\) 秒时恰好到达 \(u\) 的方案数。转移 \(f(u, t) \to f(v, t + 1)\)（\((u, v) \in \mathbb E\)）。答案为 \(\sum_{t \le T} f(1, T)\)。
第一维很小，第二维很大。矩阵快速幂即可。
对于原问题，我们考虑容斥。
首先求总方案数，即不对购买的商品进行限制，也就是上面的问题。这是全集。
减去某一种商品一定不购买的方案数。枚举那种商品一定不买。枚举每条边，如果这条边的商店里存在这种商品，把这条边断掉。
加上某两种商品一定不购买的方案数，容斥下去即可。
标签：le,10.8,路径,矩阵,lca,100,CSP,十连测 From： https://www.cnblogs.com/2huk/p/18452413