自动搬运

查看原文

来自洛谷，原作者为

	zyc2003 El Psy Congroo

搬运于2025-08-24 22:23:49，当前版本为作者最后更新于2021-07-05 10:18:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

(中二一下 , 咳咳咳

本文摘要

• 简要介绍了 $32pts$ (容斥) 的做法 , 详细介绍了 $64(72)pts$ (dp 方程的推导 , 深度的离散化 (虚树)) 和 $100pts$ (整体dp , 线段树合并) 的解法 .
• 由于我看各路大佬题解的线段树合并看了老半天没看懂 , 所以这一篇的线段树合并会讲的比较详细 , 可能更加适合像我一样没那么熟练链线段树合并的同学 .
• 同时 , 对于 dp 方程的推出有自然的想法 , 并非跳跃式的直接给出状态设计 . (不过对大佬来说确实一点都不跳跃
• 希望大家看得愉快 .

题意简述

题目中已经给出了形式化的描述 , 这里不再复述 . 为了下文叙述方便 , 我们把将一条边赋值为 $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 的方程 :

$f_{x,0/1}$ 表示 , 所有树链限制 $(u,v)$ , 其两个端点都在 $x$ 子树内的限制都已经被满足 , 而 $v$ 在 $x$ 子树内 , $u$ 在 $x$ 子树外的限制没有/有 $(0/1)$ 被全部满足 , 的方案数 . 这是我们最初的想法 .

但是这是不可转移的 , 因为我们把所有链的信息浓缩在 $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$ 的好成绩 . 我对于这部分分有实现 , 下面是离散化这部分的代码 :

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$)

#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+$ 天 , 完结撒花 !