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\) 位，每位仍然是上面的转移，差不多就是 \((0,0)\to 0,~(0,1)\to 1,~(0,2)\to 2,~(0,3)\to 3,~(1,1)\to 3\)，如果枚举每一位是哪种转移，时间复杂度是 \(O(n8^k)\)。考虑优化，把 \(0,1,3\) 聚合到 \(3\) 的位置，这样贡献只有 \((0,0)\to 0,~(0,1)\to 1,~(0,2)\to 2,~(3,3)\to 3\) 一共 \(6\) 种转移。

然后考察当前节点是否点亮，\(2\) 显然不能点亮，\(0/1\) 点亮之后既可以是 \(1\) 也可以是 \(2\)，用 \(3\) 表示，\(3\) 点亮之后还是 \(3\)。然后发现 \(1\) 和 \(3\) 时当前节点将会亮起，这样就是一次高维前缀和了，时间复杂度 \(O(n6^k+nk4^k)\)。

P14829 [THUPC 2026 初赛] Asian Soul

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

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

P3206 [HNOI2010] 城市建设

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