题解 P6383 【『MdOI R2』Resurrection】

· · 题解

这道题与传统的树形dp不同

传统的树形dp是从子树中合并答案上来

即先确定子树对祖先的影响，然后确定当前节点的影响

这道题目显然不太好这样做，因为当前考虑的点的深度变小的时候，本来有限制的现在没有了限制，这样就非常不好设状态

那么我们反过来考虑，首先确定父亲对儿子的影响 然后dp。

首先观察可以发现 最终的答案肯定是这样的形态：

而没有：

就是父亲选好以后子树的点要么选父亲选的点上面的点 要么选父亲下面的点 而没有交叉的情况（手玩得证）

这样可以设f[u][i]表示点u的上面还有i个点可供它选择去限制。每次枚举u限制了几个点，然后把儿子相应的答案乘起来

形式化的说就是f[u][i]= \sum_{j=0}^{i-1}\prod_{v} f[v][i-j+1] 加1表示下面儿子可以多u这个点

直接做是n^3的 考虑这个dp的第二维，发现由i->i+1只有一项不同，i+1每次继承i的状态 在单独算一下自己的特有的项

code：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 11;
const int mod = 998244353;
int f[N][N], n;
vector<int> G[N];
int dfs(int u, int res, int fa){
    if(f[u][res] != -1)return f[u][res];
    if(G[u].size() == 1){
        return f[u][res] = res;
    }
    int &F = f[u][res];
    F = 0;
    if(res > 1)(F += dfs(u, res - 1, fa)) %= mod;
    int sum = 1;
    int s = G[u].size();
    for(int i = 0;i < s; i++){
        int v = G[u][i];
        if(v == fa)continue;
        sum = 1LL * sum * dfs(v, res + 1, u) % mod;
    }
    F = (F + sum) % mod;
    return F;
}
int main(){
    cin>>n;
    int u, v;
    memset(f, -1, sizeof f);
    for(int i = 1;i < n; i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int ans = 1;
    int s = G[n].size();
    for(int i = 0;i < s; i++){
        int v = G[n][i];
        ans = 1ll * ans * dfs(v, 1, n) % mod;
    }
    printf("%d\n", ans);
    return 0;
}