题解：P11863 「o.OI R1」CX

· · 题解

对于这道题，我们不难发现，如果根节点的某一棵子树形状是一条链，那么我们可以选择这棵子树上的任意一个点进行覆盖这一整颗子树。

而如果一颗子树不是链，先说结论，是整个子树中从这个子树的根节点往下到第一个拥有多个儿子的节点位置，这个链状结构的节点总数。

同一棵子树选择一个点即可所以是相加关系，根的不同子树中每一棵子树都要提供一种方案所以是相乘关系，最终加上选择根节点的 1 种方案，就得到了最终结果。

例如样例这棵树：

左边这棵子树是链状，所以节点 2 和 4 都可以用来给整颗子树进行覆盖。

右边这棵子树不是链状，所以从子树的根节点 3 号节点，到往下第一个有多个儿子的位置，还是 3 号节点，中间只有 3 一个节点。

所以对于右边的子树，方案只有 1 种，再乘上左边子树的 2 种，加上选择根节点 1 的 1 种，最终得到 1\times 2 + 1 = 3 种不同的方案，也就是样例的结果。

原因：首先可以得到，对于根节点的一棵子树，我们最多只能在这棵子树里选择 1 个点对这棵子树进行覆盖，原因也很简单，如果在一棵子树里面选择超过一个点，那么这两个节点到 1 节点的路径必然有至少一段会被覆盖两次（可以自己思考一下为什么），所以不符合题目要求。

依照题意，选择一个节点以后，这个节点到 1 的路径和这个节点的子树全部被覆盖，而当子树是链的时候，相当于把整条链全部覆盖，所以每一个点都可以选。

而当子树不是链的时候，因为我们既要覆盖整颗子树，又不能选超过两个点，所以只能选择在根节点到第一个拥有多个儿子的节点这一段上，因为一旦选择在其他的节点上，就一定会有子树上的节点没有被标记（例如样例中选择在 5 节点上，6 节点就不会被标记）。这个也很明显，因为不是链的情况下，选在链以外的节点就一定会导致只有选择了的节点的子树会被覆盖到，所以就会有点没有被覆盖，又因为最多选 1 个点，所以说这样的方案就不合法。

最后加上单独选择 1 节点的这种方案，就可以得到结果了。

记得取模。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
const int Mod = 998244353;
int n,ans=1;
//这里ans初始值是1是因为为了便于下面每一棵子树的方案相乘。
//但是一定有一棵子树的方案数至少是1，所以不会影响结果
vector<int>e[N];
int dfs(int x){
    int tmp = 0; 
    if(e[x].size()>1) return 1;
    for(int i = 0; i<e[x].size(); i++){
        int v = e[x][i];
        tmp += dfs(v);
    }   
    return tmp+1;
}
signed main(){
    cin>>n;
    for(int i = 2; i<=n; i++){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    for(int i = 0; i<e[1].size(); i++){
        int v = e[1][i];
        ans*=dfs(v);
        ans%=Mod;
    }
    cout<<(ans+1)%Mod<<endl;
    return 0;
}