260117 以前 x 天

P13275 [NOI2025] 集合

考虑对第一个限制进行容斥，设 \(f_{i,S_1,S_2}\) 表示考虑了前 \(i\) 个数，\(S_1\subseteq P_i,S_2\subseteq Q_i\) 的权值和。考虑 \(f_{n,S_1,S_2}\) 对答案的贡献，设 \(g_{T}\) 表示 \(\bigcap P=\bigcap Q=T\) 的权值和，那么

\[ g_T=\sum_{T\subseteq S_1}\sum_{T\subseteq S_2}(-1)^{|S_1|+|S_2|}f_{n,S_1,S_2} \]

于是

\[ ans=\sum_{S_1}\sum_{S_2}(-1)^{|S_1|+|S_2|}2^{|S_1\cap S_2|}f_{n,S_1,S_2} \]

考虑如何求 \(f\)，可以对每一个位置分别考虑：

\[ f_{n,S_1,S_2}=\Bigl(\prod_{i=1}^{n}[S_1\subseteq i](1+a_i)\Big)\Bigl(\prod_{i=1}^{n}[S_2\subseteq i](1+a_i)\Big)\Bigl(\prod_{i=1}^{n}[S_1\subseteq i\wedge S_2\subseteq i]\frac{(1+2a_i)}{(1+a_i)^2}\Big) \]

然后搞一搞就可以用或卷积 fwt 做了，需要扩域。

P10674 【MX-S1-T3】电动力学

先建出圆方树，然后设出状态 \(f_{u,0/1/2/3}\) 表示子树里没有点/钦定子树内外都有点/钦定只有子树内有点/子树外有没有都行 的贡献和。发现根据状态我们可以唯一确定当前点的贡献。于是对圆点和方点分别转移即可，注意如果一个 bcc 内有至少两棵子树内有关键点，那么 bcc 内其他圆点也会产生 \(2\) 的贡献。

P10717 【MX-X1-T5】「KDOI-05」简单的树上问题

把 0/1/2/3 的状态压成 \(k\) 位，还是上面的转移。由于合并子树的地方转移多达 \(8\) 种需要优化，发现可以对 \(3\) 状态进行容斥，先算出全部（不包含 \(2\)）的方案数，再减去只有 0 和只有一个 1 的方案数，需要提前对子树的 dp 数组和自己的 dp 数组进行高维前缀和。

剩下的枚举当前节点的状态，也需要高维前缀和优化。

P14829 [THUPC 2026 初赛] Asian Soul

首先可以分块，预处理每个点向每个块的贡献，时间复杂度 \(O(n\sqrt n)\)。

尝试使用线段树，由于线段树有 \(O(n)\) 个区间所以显然不能预处理每个点到每个区间的答案。但注意到我们只关心询问的那些点，所以实际上只有 \(O(q\log n)\) 对贡献。求出每个区间的虚树，还要把询问的点也加进去，然后就做完了。

P3206 [HNOI2010] 城市建设

考虑线段树分治，考虑根链上所有节点包含的边，把必须要加的边全都加入，把加不了的边直接扔掉，此时保留下来的边一定形成森林，并且数量不超过子树节点内的边数（一般是区间长度，但在 1 和 n 不是）。