专栏文章

题解：P5007 DDOSvoid 的疑惑

ssmall_add_add
P5007题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mink11lk
此快照首次捕获于
2025/12/02 03:40
3 个月前
此快照最后确认于
2025/12/02 03:40
3 个月前
查看原文
弱鸡第一次写题解，大佬们看着玩就行orz

一、问题重述

给定一棵以 11 为根的树，‌毒瘤集‌是满足以下条件的节点集合：
集合中任意两个节点不存在祖先-后代关系 （即任意节点不能是另一个的父节点、祖父节点等） 毒瘤指数定义为集合内所有节点的权值之和（ T=1T=1 时节点权值为编号，T=0T=0 时权值均为 11 ） ‌
目标‌：计算所有可能毒瘤集的毒瘤指数总和，结果对 1e8+71e8+7 取模。
我就因为看成了1e9+7卡了好久

二、核心思路：集合合并视角的DPDP

传统树形DP通常定义"选/不选"状态，这里我们从‌集合生成‌角度构建新模型：
‌定义两个关键数组‌（针对以u为根的子树）：
dp[u]dp[u] ：所有毒瘤集的毒瘤指数总和
sz[u]sz[u] ：毒瘤集的总个数（包含空集） ‌
具体为什么包含空集合请看下面

核心发现‌：子树合并时的集合运算规律

若 A、BA、B 是 两棵独立子树的毒瘤集集合（元素无交集），则合并后的毒瘤集集合为：
A+B=X∣X=a∪b,a∈A,b∈BA+B = {X | X = a ∪ b, a ∈ A, b ∈ B}
此时毒瘤指数总和满足：
‌ value(A+B)=value(A)×∣B∣+value(B)×∣A∣‌value(A+B) = value(A)×|B| + value(B)×|A|‌
推导：
value(A+B)value(A+B) =∑i=1∣A∣∑j=1∣B∣∑Ai∪Bj =\sum_{i=1}^{|A|} \sum_{j=1}^{|B|}\sum A_i∪B_j
由于 A、BA、B 是两棵 独立子树（元素无交集） 的毒瘤集集合，于是：
原式=∑i=1∣A∣∑j=1∣B∣(∑k=1∣Ai∣Ai,k+∑k=1∣Bj∣Bj,k)原式=\sum_{i=1}^{|A|} \sum_{j=1}^{|B|}(\sum_{k=1}^{|A_i|}A_{i,k} + \sum_{k=1}^{|B_j|}B_{j,k})
=(∑i=1∣A∣∑j=1∣B∣∑k=1∣Ai∣Ai,k)+(∑i=1∣A∣∑j=1∣B∣∑k=1∣Bi∣Bi,k)=(\sum_{i=1}^{|A|} \sum_{j=1}^{|B|}\sum_{k=1}^{|A_i|}A_{i,k})+ (\sum_{i=1}^{|A|} \sum_{j=1}^{|B|}\sum_{k=1}^{|B_i|}B_{i,k})
=∣B∣∑i=1∣A∣∑j=1∣Ai∣Ai,j+∣A∣∑i=1∣B∣∑j=1∣Bi∣Bi,j=|B|\sum_{i=1}^{|A|}\sum_{j=1}^{|A_i|} A{i,j}+|A|\sum_{i=1}^{|B|}\sum_{j=1}^{|B_i|} B{i,j}
=∣B∣value(A)+∣A∣value(B)=|B|value(A)+|A|value(B)
（本质是每个集合的元素会与另一集合的所有集合组合）
第一次用LaTex写的比较丑Sorry
要包含空集的原因
这时我们就能解释为什么要包含空集了
集合合并中，空集 ∅\empty 是“单位元”：
任何集合 AA 与空集合并后仍为 A（A∪∅=A)A（A ∪ \empty = A)
如果不包含空集，合并子树时会‌漏掉大量合法毒瘤集‌。
例如：两个子树的毒瘤集分别为 A{A} 和 B{B}（不含空集）， 则合并后只能生成 A,B{A,B} 但实际合法毒瘤集还包括 A、B{A}、{B}（需通过空集合并：A∪∅=A，∅∪B=B）{A} ∪ \empty = {A}，\empty ∪ {B} = {B}）
AmazingAmazing 啊!现在我们就可以写 DPDP 了

三、分阶段 DPDP 推导

1. 叶子节点的初始化

叶子节点u只有两种毒瘤集：空集 ∅\empty 和 u{u}
CPP
if(G[u].size()==1){
    sz[u]=2ll; 
    dp[u]=(T?u:1ll);
    return;
}

2. 非叶子节点的合并

假设 uu 有 kk 个子节点 v1,v2,...vkv_1,v_2,...v_k，合并过程分两步：

‌Step 1：合并所有子树的毒瘤集‌

初始状态：dp[u]=0，sz[u]=1dp[u] = 0，sz[u] = 1（仅空集）
依次合并每个子树 vv：
CPP
int cnt=0;
for(int v:G[u]){
	if(v==fa)continue;
	Dfs(v,u);
	cnt++;
	if(cnt==1){
		sz[u]=sz[v];
		dp[u]=dp[v];
	}
	else{
		dp[u]=dp[u]*sz[v]+dp[v]*sz[u];
		sz[u]*=sz[v];
		dp[u]%=mod;
		sz[u]%=mod;
	}
}

‌Step 2：加上当前点

CPP
dp[u]+=(T?u:1);
sz[u]++;
dp[u]%=mod;
sz[u]%=mod;
（因为空集的贡献为0，所以不用特殊处理）

四.代码

CPP
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
LL const mod=1e8+7;
LL const N=1e6+5;
LL dp[N],sz[N];
int n,T;
vector<int>G[N];
void Dfs(int u,int fa){
	if(G[u].size()==1){
		sz[u]=2ll; // {},{u}
		dp[u]=(T?u:1ll);
		return;
	}
	int cnt=0;
	for(int v:G[u]){
		if(v==fa)continue;
		Dfs(v,u);
		cnt++;
		if(cnt==1){
			sz[u]=sz[v];
			dp[u]=dp[v];
		}
		else{
			dp[u]=dp[u]*sz[v]+dp[v]*sz[u];
			sz[u]*=sz[v];
			dp[u]%=mod;
			sz[u]%=mod;
		}
	}
	dp[u]+=(T?u:1);
	sz[u]++;
	dp[u]%=mod;
	sz[u]%=mod;
}
signed main(){
	cin>>n>>T;
	for(int i=1;i<n;i++){
		int u,v; cin>>u>>v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	Dfs(1,0);
	cout<<dp[1];
	return 0;
}
完结撒花

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...