分析

本题初看没有任何思路
但经过长达1个小时（有点夸张）的端详
我们可以注意到
对于一个图中所说的包含部分叶子的虚树
上边的节点分为两类

作为一条边经过，即：当前被染色，并且染了他的一个儿子
作为一个LCA经过，即：当前节点被染色，并且它的两个及以上节点被染色

为什么我们需要分开1个儿子和两个及以上儿子呢？
因为第一种情况无法作为当前虚树的根节点
反之，第二种情况就是可以的
当然，对于整棵树来说，就还有一种类型的节点

没有被染色

想到这里，剩下的工作也就不太麻烦了，只是转移非常的细节
我们设
DP[][0]表示上边的第三种情况
DP[][1]表示上边的第一种情况
DP[][2]表示上边的第二种情况
所以我们可以得到以下的转移方程式

$DP[\,u\,][\,0\,] = DP[\,v\,][\,0\,] \times (DP[\,v\,][\,0\,] + DP[\,v\,][\,2\,]) \\ DP[\,u\,][\,1\,] = DP[\,u\,][\,0\,] \times (DP[\,v\,][\,1\,] + DP[\,v\,][\,2\,]) + DP[\,u\,][\,1\,] \times (DP[\,v\,][\,0\,] + DP[\,v\,][\,2\,]) \\ DP[\,u\,][\,2\,] = DP[\,u\,][\,1\,] \times (DP[\,v\,][\,1\,] + DP[\,v\,][\,2\,]) + DP[\,u\,][\,2\,] \times (DP[\,v\,][\,0\,] + DP[\,v\,][\,1\,] + 2 \times DP[\,v\,][\,2\,])$

至于为什么最后一个转移中会有DP[v][2]*2呢？
因为这个 $v$ 点，可能是和当前节点一个虚树上的，也可能是另一棵虚树上的

代码

//CF1146F
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f3f3f3f3f
#define Mod 998244353
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=2e5+10;

LL DP[MaxN][3];
LL Total,u,v,w,D[MaxN];
LL Next[MaxN<<1],Head[MaxN],End[MaxN<<1],Cur;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void DFS(LL New,LL Pre) {
    if(D[New]==1 && New!=1) { DP[New][2]=1; }
    else { DP[New][0]=1;}
    for(LL i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        DFS(End[i],New);
        LL Zero=DP[New][0],One=DP[New][1],Two=DP[New][2];
        DP[New][0]=Zero*((DP[End[i]][0]+DP[End[i]][2])%Mod)%Mod;
        (DP[New][1]=One*((DP[End[i]][0]+DP[End[i]][2])%Mod)%Mod+Zero*((DP[End[i]][1]+DP[End[i]][2])%Mod)%Mod)%=Mod;
        (DP[New][2]=One*((DP[End[i]][1]+DP[End[i]][2])%Mod)%Mod+Two*((DP[End[i]][0]+DP[End[i]][1]+2LL*DP[End[i]][2]%Mod)%Mod)%Mod)%=Mod;
    }
}

inline void Add_Edge(LL From,LL To) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;
}

signed main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Total;
    FOR(i,2,Total) { cin>>u; Add_Edge(u,i); Add_Edge(i,u); D[u]++; D[i]++; }
    DFS(1,0);
    // FOR(i,1,Total) 
    //     cout<<"i: "<<DP[i][0]<<" "<<DP[i][1]<<" "<<DP[i][2]<<endl;
    cout<<(DP[1][0]+DP[1][2])%Mod<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}

Leaf Partition

分析

代码