P12844 [蓝桥杯 2025 国 A] 树 题解

· · 题解

我们首先根据题目中所说的“使得选择的任意两点之间的距离均大于 2”这个限制条件推点东西出来。

首先最直白的，选了自己就不能选儿子和孙子了。

然后就是，如果不选自己要选儿子的话，最多只能选一个儿子。选了两个的话，它们之间的距离就是 2 了。

以及，如果不选自己，儿子能不能选是不确定的（因为这得看选没选父亲），但是孙子一定是不受影响的。

考虑树形 DP。定义 dp_{u,0/1} 分别表示选与不选 u 的情况总数，最终答案就是 dp_{root,0} + dp_{root,1}，其中 root 是根，我们可以自定义为 1。

但是根据上面几条限制，我们会发现，选不选儿子节点对该节点的决策非常重要。那现在的状态定义就不够全面了。

扩展它。定义 dp_{u,0} 表示不选 u 自己也不选任何一个儿子，dp_{u,1} 表示选 u 自己但是不选任何一个儿子，dp_{u,2} 表示不选 u 自己但是选恰好一个儿子。

那最终答案就是 dp_{root,0} + dp_{root,1} + dp_{root,2}。

于是接下来考虑转移。

转移式都得到了。dp_{u,0} 和 dp_{u,1} 是简单的，但是我们发现 dp_{u,2} 的转移如果按照这个来枚举 v 和 w 两个一起的话，你的时间复杂度就会呈 O(n^2) 的级别。

爆了！怎么办呢？我们想要能快速求出转移式中后面 \prod_{w \in son(u) \space \text{and} \space w \not= v} (dp_{w,0} \times dp_{w,2}) 的这一部分。发现这里只有 w=v 的情况被剔除了，考虑先遍历所有儿子求一个总的 \prod_{w \in son(u)} (dp_{w,0} \times dp_{w,2})，之后再枚举 v 去做转移，乘法逆元把总乘积中 v 的那一项除掉就好了。

这样你会遍历你的儿子两遍，一遍往下递归并求上面提到的那个总乘积，还有一遍分别进行转移。

一定一定一定要时刻注意取模，不然炸了就老实了。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 3e5+5;
const LL MOD = 998244353;
LL n,dp[N][3];
vector<int> g[N];
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
LL QP(LL x,LL y){
    LL as=1;
    while(y){
        if(y&1)as=as*x%MOD;
        x=x*x%MOD,y>>=1;
    }return as;
}
void DFS(int u,int fa){
    LL res=1;dp[u][0]=1,dp[u][1]=1;
    for(int v:g[u])if(v^fa)
        DFS(v,u),res=res*(dp[v][0]+dp[v][2])%MOD;
    for(int v:g[u])if(v^fa)
        dp[u][0]=dp[u][0]*(dp[v][0]+dp[v][2])%MOD,
        dp[u][1]=dp[u][1]*dp[v][0]%MOD,
        dp[u][2]+=(dp[v][1]*(res*QP(dp[v][0]+dp[v][2],MOD-2)%MOD))%MOD,
        dp[u][2]%=MOD;
    return;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        g[x].pb(y),g[y].pb(x);
    }DFS(1,0);
    cout<<(dp[1][0]+dp[1][1]+dp[1][2]-1)%MOD;
    return 0;
}

哎呀，忘了个事。你是不是发现我最后代码那里的输出多了个 -1？这是咋回事？哈哈，因为题目明确要求了不能不选，但是我们前面的 DP 可都没考虑这点啊，不过没关系，我们只要把这题目不允许出现的一次减掉就可以了。

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！