首页 / ACCESS / dtoj4700 Access

dtoj4700 Access

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了dtoj4700 Access，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1968字，纯文字阅读大概需要3分钟。

内容图文

在一棵有根树中，边有两种：虚边和实边。一个点最多和一个儿子之间有实边。

当我们执行 Access(x) 时，首先会把 x 到根这条路径上的所有点的实边全变成虚边，然后把这条路径上的所有边全变成实边。

有一棵 $n$ 个点、以 $1$ 为根的有根树，一开始所有边都是虚边。你可以进行最多 $k$ 次任意的 access 操作，求树有可能的形态数目。

Sol

什么？？树形dp的效率是O(nk)的？？！！

 

考虑dp.

f[i][j]表示以i为根的子树进行了j次有效的access。

那么有树形dp的时候g[i][j][0/1]表示前i棵子树，进行了j次有效的access，否/是 选出了一条v->k的实边。

g[i][j+x][0]=f[v][x]*g[i-1][j][0]

g[i][j+x][1]=f[v][x]*g[i-1][j][1]

这两种相当于v不连上去

g[i][j+x][1]=g[i-1][j][0]*(f[v][x]+(x==1))

相当于我选择v连上去。但是如果x==1，那么f[v][1]少包括了只 access v 的情况所以要加1。

技术分享图片 技术分享图片 
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 10005
#define ll long long
#define mod 998244353 
usingnamespace std;
int n,m,head[maxn],tot,t[maxn],cnt,sz[maxn];
ll f[maxn][505],g[maxn][505][2];
struct node{
    int v,nex;
}e[maxn*2];
void add(int t1,int t2){
    e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
}
void dp(int k,int fa){
    sz[k]=1;  
    for(int i=head[k];i;i=e[i].nex){
        if(e[i].v^fa)dp(e[i].v,k),sz[k]+=sz[e[i].v];
    }
    cnt=0;
    for(int i=head[k];i;i=e[i].nex){
        if(e[i].v^fa)t[++cnt]=e[i].v;
    }
    g[0][0][0]=1;int Sum=0;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<=Sum&&j<=m;j++){
            for(int x=0;x<=sz[t[i]]&&x+j<=m;x++){
                (g[i][j+x][0]+=g[i-1][j][0]*f[t[i]][x]%mod)%=mod;
                (g[i][j+x][1]+=g[i-1][j][1]*f[t[i]][x]%mod)%=mod;
                if(x)(g[i][j+x][1]+=g[i-1][j][0]*(f[t[i]][x]+(x==1))%mod)%=mod;
            }
        }
        Sum+=sz[t[i]];
    }
    f[k][0]=1;
    for(int i=1;i<=sz[k]&&i<=m;i++){
        f[k][i]=g[cnt][i][1];
        if(i>1)(f[k][i]+=g[cnt][i-1][0])%=mod;
    }
    Sum=0;
    for(int i=1;i<=cnt;i++){
        Sum+=sz[t[i]];for(int j=0;j<=Sum&&j<=m;j++)g[i][j][0]=g[i][j][1]=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1,t1,t2;i<n;i++){
        scanf("%d%d",&t1,&t2);
        add(t1,t2);add(t2,t1);
    }
    dp(1,0);
    ll ans=0;
    for(int i=1;i<=m;i++)ans=(ans+f[1][i])%mod;
    cout<<ans+1<<endl;
    return0;
}
View Code

 

原文：https://www.cnblogs.com/liankewei/p/12388281.html

内容总结

以上是互联网集市为您收集整理的dtoj4700 Access全部内容，希望文章能够帮你解决dtoj4700 Access所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1272455.html

来源：【匿名】