题解：P5007 DDOSvoid 的疑惑

· · 题解

弱鸡第一次写题解，大佬们看着玩就行orz

一、问题重述

给定一棵以 1 为根的树，‌毒瘤集‌是满足以下条件的节点集合：

集合中任意两个节点不存在祖先-后代关系 （即任意节点不能是另一个的父节点、祖父节点等） 毒瘤指数定义为集合内所有节点的权值之和（ T=1 时节点权值为编号，T=0 时权值均为 1 ） ‌

目标‌：计算所有可能毒瘤集的毒瘤指数总和，结果对 1e8+7 取模。

我就因为看成了1e9+7卡了好久

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

传统树形DP通常定义"选/不选"状态，这里我们从‌集合生成‌角度构建新模型：

‌定义两个关键数组‌（针对以u为根的子树）：

dp[u] ：所有毒瘤集的毒瘤指数总和

sz[u] ：毒瘤集的总个数（包含空集） ‌

具体为什么包含空集合请看下面

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

若 A、B 是 两棵独立子树的毒瘤集集合（元素无交集），则合并后的毒瘤集集合为：

A+B = {X | X = a ∪ b, a ∈ A, b ∈ B}

此时毒瘤指数总和满足：

‌

value(A+B) = value(A)×|B| + value(B)×|A|‌

推导：

value(A+B) =\sum_{i=1}^{|A|} \sum_{j=1}^{|B|}\sum A_i∪B_j

由于 A、B 是两棵 独立子树（元素无交集） 的毒瘤集集合，于是：

原式=\sum_{i=1}^{|A|} \sum_{j=1}^{|B|}(\sum_{k=1}^{|A_i|}A_{i,k} + \sum_{k=1}^{|B_j|}B_{j,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|\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)

（本质是每个集合的元素会与另一集合的所有集合组合）

第一次用LaTex写的比较丑Sorry

要包含空集的原因

这时我们就能解释为什么要包含空集了

集合合并中，空集 \empty 是“单位元”：

任何集合 A 与空集合并后仍为 A（A ∪ \empty = A)

如果不包含空集，合并子树时会‌漏掉大量合法毒瘤集‌。

例如：两个子树的毒瘤集分别为 {A} 和 {B}（不含空集）， 则合并后只能生成 {A,B} 但实际合法毒瘤集还包括 {A}、{B}（需通过空集合并：{A} ∪ \empty = {A}，\empty ∪ {B} = {B}）

## 三、分阶段 $DP$ 推导 ### 1. 叶子节点的初始化 叶子节点u只有两种毒瘤集：空集 $\empty$ 和 ${u} 
if(G[u].size()==1){
    sz[u]=2ll; 
    dp[u]=(T?u:1ll);
    return;
}

2. 非叶子节点的合并

假设 u 有 k 个子节点 v_1,v_2,...v_k，合并过程分两步：

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

初始状态：dp[u] = 0，sz[u] = 1（仅空集）

依次合并每个子树 v：

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：加上当前点

dp[u]+=(T?u:1);
sz[u]++;
dp[u]%=mod;
sz[u]%=mod;

（因为空集的贡献为0，所以不用特殊处理）

四.代码

#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;
}

完结撒花