[NOI2020 : 命运] 题解

· · 题解

这一切 , 都是 \lfloor 命运 \rceil 石之门的选择 !

(中二一下 , 咳咳咳

本文摘要

题意简述

题目中已经给出了形式化的描述 , 这里不再复述 . 为了下文叙述方便 , 我们把将一条边赋值为 1 说成是染了色 , 把题目给出的带限制的链有时候简称为一个限制 .

32pts : 容斥大法好 !

看到题目后 , 我一开始心态是崩的 : 我怎么只有 n\times 2^n 的枚举算法 ? 完了呀 ... 但是你冷静一下 , 前面 40pts 的 m 都很小 - 也就是给定的树链 (u,v) 很少 , 有什么用呢 ?

题目要求的是 : 所有给定的树链 , 其链上至少有 1 条边被染色的方案数 . 我对着它冥思苦想 ... 没什么思路 , 不妨取问题的补集 , 也就是逆向思维 ? 可以等价于任意染色/不染色的方案数 (2^{n-1}) , 减去 : 至少存在一条给定树链 , 其链上没有边被染色的方案数 .

到了这里 , 就可以使用我们的容斥大法 . 枚举所有 m 的子集 S , 求出这个子集中所有被给定树链覆盖的边都不能染色的染色方案数 , 再乘以容斥系数 (-1)^{|S|} 即可 . 该算法正确是因为 , 当 |S|=0 时 , 我们加上了任意染色的方案数 2^{n-1} : 此时所有合法的和不合法的方案都在里面 ; 当 |S|=1 时 , 我们减去了 第 1 条链 , 第 2 条链 , \dots , 第 m 条链上没有任何一条边被染色的方案数 ; 但是这些链是会相交的 , 我们多减去了一些东西 , 所以我们还需要加上第 i 条链和第 j 条链均没有任何一条边被染色的方案数 ... 归纳地证明了容斥的正确性 . 写成式子 , 就是 :

\sum_{S\subset Q} (-1)^{|S|} 2^{n-1-|\cup_S|}

其中 Q 是题目给定的树链的集合 , |\cup_S| 表示 S 集合内的树链求交之后 , 覆盖的边数 .

而我们发现 , 覆盖一条链的操作可以用树链剖分维护 , 所以总复杂度为 : \mathcal O(m\times 2^m \log^2n) , 也可以优化到 \mathcal O(2^m \log^2n) (不过没什么用 , 得分没有变化 ... 所以我 40pts 的美梦破灭了

64pts : dp 大法好 !

实际上容斥的做法 , 对于参加 NOI 的选手可能是小菜一碟的 . 那么更进一步的做法呢 ? 求方案数嘛 , 怎么想都和 dp 脱不了关系 . 而树上 dp 的设计肯定和子树有关 , 不妨先设计一个最 naive 的方程 :

但是这是不可转移的 , 因为我们把所有链的信息浓缩在 $0/1$ 中 , 以至于我们从子节点 $y$ 向父节点 $x$ 转移时 , 我们无法确定边 $(x,y)$ 染色/不染色会造成的影响 . 主要影响是 , 当某个限制 $(u,v)$ 满足 $u=x$ , 且 $v$ 在 $y$ 的子树内时 , 从 $y$ 向 $x$ 的转移就出了问题 : 你不懂何时需要覆盖 $(x,y)$ 何时不需要 , 因为你不懂 $(u,v)$ 这个限制是否已经在 $y$ 的子树内得到满足 ! 那我们尝试维护这个信息如何 ? 但是注意到 , $y$ 转移到 $x$ , $x$ 又会转移到 $x$ 的父亲 ... 这可能要求我们维护一个和深度有关的信息 . 一端 $u$ 在 $x$ 的子树外 , 一端 $v$ 在 $x$ 的子树内 , 那么显然所有 $u$ 都是 $x$ 的祖先 ... 等等 , 所有 $u$ 都是 $x$ 的祖先 ? 在看看题目的要求 : 所有给定链上至少有 $1$ 条边被染色 . 那么这就意味着 , 我们考虑所有尚未被满足的 $(u,v)$ , 且 $u$ 在 $x$ 子树外 , $v$ 在 $x$ 子树内 , 那么能使得它们合法的染色只可能是将 $(u,x)$ 中的某条边染色 ; 而最终情况下 , 必须让所有限制都合法 , 所以我们必须所有给 $u$ 中最深的 $(u_{\max},x)$ 中的某条边染色 ; 染色了 , 所有限制一并满足 ; 如果不是给 $(u_{\max},x)$ 上的某条边染色 , 那么 $(u_{\max},v)$ 这个限制将永远得不到满足 . 这就是其他题解中所说的 key observation . 所以 , 我们的 dp 方程新鲜出炉 : 设 $f_{x,i}$ 表示 $x$ 为根的子树中 , 两端点都在 $x$ 子树内的限制已经被满足 , 而对于尚未被满足的 $(u,v)$ , 且 $u$ 在 $x$ 子树外 , $v$ 在 $x$ 子树内 , 最深的 $u$ 的深度为 $i$ . 现在来考虑转移 . 首先 , 如果对于一个 $v$ , 题目给出了多个限制 $(u_1,v),(u_2,v)\dots$ , 那么最深的那个 $u$ 是有用的 . 设 $anc_v=u$ (ancestor , 祖先) , 当 $anc_v=0$ 时 , 说明没有限制 , 或者也可以认为是设置了虚点 $0$ , 该限制为 $(0,v)$ . 那么 , 对于 $f_{x,i}$ , 我们有 $\mathrm{dep}_{anc_x} \leq i < \mathrm{dep}_x$ , 因为对于限制 $(anc_x,x)$ , 无论你怎么给 $x$ 子树内的边染色 , 都不可能满足 ; 而 $i$ 也不能取到 $\mathrm{dep}_x$ (显然) . 好 . 接下来推导 $y\rightarrow x$ 的转移 . 当处理到子节点 $y$ 的时候 , $f_{x,i}$ 的值如何变化 : $1.$ 对 $(x,y)$ 染色 那么所有端点 $v$ 在 $y$ 内的限制全部得到满足 . 所以贡献为 $$f_{x,i}\times \sum_{\mathrm{dep}_{anc_y} \leq j < \mathrm{dep}_y} f_{y,j}$$ 噢 , 为了方便 , 不妨设 $g_{x,i}$ 为 $f_{x,i}$ 的前缀和 : $g_{x,i}=\sum_{j=0}^i f_{x,i}$ , 由于 $ < \mathrm{dep}_{anc_x}$ 的部分都为 $0$ , 所以这个定义是合法的 . 所以贡献为 : $$f_{x,i}\times g_{y,\mathrm{dep_y}-1}$$ $2.$ 对 $(x,y)$ 不染色 那么 , 如果 $y$ 中最深的限制是 $\leq i$ 的 , 那么合并后的子树的最深的限制仍然是 $i$ . 所以 , 贡献为 : $$f_{x,i}\times g_{y,i}$$ 但如果是 $>i$ 的 , 那么最深的限制可以有更浅的限制转移而来 , 贡献为 : $$g_{x,i-1}\times f_{y,i}$$ 整合起来就是 : $$f_{x,i}\leftarrow f_{x,i}\times g_{y,\mathrm{dep_y}-1}+f_{x,i}\times g_{y,i}+g_{x,i-1}\times f_{y,i},\mathrm{dep}_{anc_x} \leq i < \mathrm{dep}_x$$ 这样就有了 $\mathcal O(n^2)$ 的做法 . 但是注意到 , 有用的点 , 也就是作为限制的点 $u$ 是 $\mathcal O(\min(n,m))$ 级别的 . 所以 , 第二维 : 深度是可以离散化的 . 离散化后的第二维是 $\mathcal O(\min(n,m))$ 级别的 , 所有时空复杂度均为 $\mathrm O(n\min(n,m))$ , 可以拿到 $64pts$ 的好成绩 . 我对于这部分分有实现 , 下面是离散化这部分的代码 : ```cpp int main() { n=read(); for(int i=1,x,y;i<n;++i) x=read(),y=read(),add(x,y),add(y,x); dfs(1,0); m=read();dep[0]=0; for(int i=1;i<=m;++i) { int u=read(),v=read(); anc[v]=dep[u] > dep[anc[v]] ? u : anc[v]; } for(int i=1;i<=n;++i) if(anc[i]) rk[++cnt]=dep[anc[i]]; sort(rk+1,rk+1+cnt),cnt=unique(rk+1,rk+1+cnt)-rk-1; rk[++cnt]=n; for(int i=1;i<=n;++i) dep[i]=lower_bound(rk+1,rk+1+cnt,dep[i])-rk; treedp(1,0); Writes(f[1][0]); return 0; } ``` Q : 那么 $f,g$ 数组怎么开 ? A : 当然是用 vector 啦 ! Q : 你为什么不用虚树 ? 你这样写 , $15,16$ 两个点会爆空间啊 ! $nm=10^9$ ... A : 我忘记虚树了 ... 用虚树的话 , 时空复杂度变为 $\mathcal O(\min(n,m)^2)$ , 足以解决 $72pts$ 的问题 . ### $100pts$ : 整体 dp - 线段树合并 ! 好吧 , 这部分我无法自然地想出 qaq ... 我们对式子进行一些变化 : $$f_{x,i}\leftarrow f_{x,i}\times (g_{y,\mathrm{dep_y}-1}+ g_{y,i})+f_{y,i}\times g_{x,i-1}$$ 发现是对 $f_{x,i}$ 乘上某个数在加上 $f_{y,i}$ 乘上某个数 , 但是所谓的"这个数"是会变的啊 ? 不要紧 . 我们仍然考虑线段树合并 . 一开始 , 令 $f_{x,\mathrm{dep}_{anc_x}}=1$ . 维护两个全局值 $sum_x,sum_y$ , 来表示 $f_{x,i}/f_{y,i}$ 的前缀和 . 前缀和可以以**引用**的形式 (引用变量 , 或者设为全局变量也可以) , 在进入叶子结点或者 $x=0$ 或者 $y=0$ 时更新 . 而后在合并 $x$ 的子树和 $y$ 的子树时 : 我们发现难点在于当 $x=0$ 或者 $y=0$ 时 , 应该怎么维护下面的值呢 ? 当我们进入 $x=0$ 或者 $y=0$ 的结点时 , 看到我们的式子 , 就会发现 : $x=0,y\neq 0$ 时 , 说明在该结点内 $sum_x$ 将不会变化 , 且所有 $f_{x,i}$ 没有值 , 那么相当于整个子树全部同乘以一个数 : $g_{x,i-1}$ ; 而当 $x\neq 0,y=0$ 时 , 说明在该结点内 $sum_y$ 将不会变化 , 且所有 $f_{y,i}$ 没有值 , 那么相当于整个子树全部同乘以一个数 : $g_{y,\mathrm{dep_y}-1}+ g_{y,i}$ ; 而 $x\neq 0,y\neq 0$ 时 , 显然我们会继续往下合并 , 只需要 pushup 即可 . 而后需要注意 , 对于 $f_{x,i}$ , 由于只有 $\mathrm{dep}_{anc_x} \leq i < \mathrm{dep}_x$ 会有值 , 所以处理完子树转移后 , 我们需要将 $[0,\mathrm{dep_{anc_x}})$ 和 $[\mathrm{dep}_x,n]$ 区间赋值为 $0$ . (覆盖总是没问题的 , 不覆盖可能会出锅) 综上 , 我们维护区间和和乘法标记即可 (区间赋值为 $0$ 可以将乘法标记设为 $0$) ```cpp #define Lx (T[x].l) #define Rx (T[x].r) #define Ly (T[y].l) #define Ry (T[y].r) #define mid ((l+r)>>1) int newp() {++cnt,T[cnt].mul=1;return cnt;} void pushup(int x) {T[x].v=qmod(T[Lx].v+T[Rx].v);} void pushdown(int x) { if(T[x].mul == 1) return ; T[Lx].mul=1ll*T[Lx].mul*T[x].mul%mod,T[Lx].v=1ll*T[Lx].v*T[x].mul%mod; T[Rx].mul=1ll*T[Rx].mul*T[x].mul%mod,T[Rx].v=1ll*T[Rx].v*T[x].mul%mod; T[x].mul=1; } void insert(int x,int l,int r,int p) { if(l == r) {T[x].v=1;return ;} if(p <= mid) Lx=newp(),insert(Lx,l,mid,p); else Rx=newp(),insert(Rx,mid+1,r,p); pushup(x); } int merge(int x,int y,int l,int r,int &sumx,int &sumy) { if(!x and !y) return 0; if(!x) { sumy=qmod(sumy+T[y].v); T[y].mul=1ll*T[y].mul*sumx%mod,T[y].v=1ll*T[y].v*sumx%mod; return y; } if(!y) { sumx=qmod(sumx+T[x].v); T[x].mul=1ll*T[x].mul*sumy%mod,T[x].v=1ll*T[x].v*sumy%mod; return x; } if(l == r) { sumx=qmod(sumx+T[x].v); T[x].v=qmod(1ll*T[x].v*sumy%mod+1ll*T[y].v*sumx%mod); sumy=qmod(sumy+T[y].v); return x; } pushdown(x),pushdown(y); Lx=merge(Lx,Ly,l,mid,sumx,sumy); Rx=merge(Rx,Ry,mid+1,r,sumx,sumy); pushup(x); return x; } void cover(int x,int l,int r,int ql,int qr) { if(!x) return ; if(ql <= l and r <= qr) {T[x].mul=0,T[x].v=0;return ;} pushdown(x); if(ql <= mid) cover(Lx,l,mid,ql,qr); if(qr > mid) cover(Rx,mid+1,r,ql,qr); pushup(x); } int query(int x,int l,int r,int p) { if(!x) return 0; if(l == r) return T[x].v; pushdown(x); return p<=mid?query(Lx,l,mid,p):query(Rx,mid+1,r,p); } void treedp(int x,int fa) { root[x]=newp(); insert(root[x],0,maxdep,dep[anc[x]]); for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y == fa) continue; treedp(y,x); int sumx=0,sumy=T[root[y]].v;//g_{y,dep_y-1} root[x]=merge(root[x],root[y],0,maxdep,sumx,sumy); } cover(root[x],0,maxdep,dep[x],maxdep); } ``` 我从开始看这道题 , 然后写部分分 , 写正解 , 写题解 ... 一共断断续续地经过了 $10+$ 天 , 完结撒花 !