#4700. Access

题目描述

题解

今天明明没什么难题还打得这么烂可见我太菜了

考虑一个被access过的树，如果把一些没有经历过虚实边转化的虚边删去的话，那我们可以发现剩下的虚边条数对应的就是这棵树被access过的最小次数-1

于是可以考虑dp： $f_{u,i}$ 表示 $u$ 子树内有i条经历了虚实边转化的虚边，考虑转移的时候要注意 $u$ 这个点最多连结一个实儿子。特殊的，一棵树是空的也要特殊处理。

代码

#include <bits/stdc  .h>
using namespace std;
const int N=10005,M=505,P=998244353;
int n,m,hd[N],sz[N],V[N<<1],nx[N<<1],t,f[N][M],s,g[N][M][2],G[M][2];
void add(int u,int v){
    nx[  t]=hd[u];V[hd[u]=t]=v;
}
void dfs(int u,int fr){
    sz[u]=g[u][0][0]=1;
    for (int v,i=hd[u];i;i=nx[i]){
        if ((v=V[i])==fr) continue;dfs(v,u);
        for (int j=0;j<sz[u] && j<m;j  )
            for (int k=0;k<sz[v] && k j<m;k  ){
                if (j k 1<m)
                    (G[j k 1][0] =1ll*g[u][j][0]*f[v][k]%P)%=P,
                    (G[j k 1][1] =1ll*g[u][j][1]*f[v][k]%P)%=P;
                (G[j k][1] =1ll*g[u][j][0]*f[v][k]%P)%=P;
            }
        for (int j=0;j<m;j  )
            (G[j][0] =g[u][j][0])%=P,
            (G[j][1] =(g[u][j][0] g[u][j][1])%P)%=P;
        for (int j=0;j<m;j  )
            g[u][j][0]=G[j][0],G[j][0]=0,
            g[u][j][1]=G[j][1],G[j][1]=0;
        sz[u] =sz[v];
    }
    for (int j=0;j<m;j  )
        f[u][j]=(g[u][j][0] g[u][j][1])%P;
    f[u][0]=(f[u][0] P-1)%P;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1,x,y;i<n;i  )
        scanf("%d%d",&x,&y),
        add(x,y),add(y,x);
    dfs(1,0);
    for (int i=0;i<m;i  )
        (s =f[1][i])%=P;
    cout<<(s 1)%P<<endl;
    return 0;
}