首页 / ACCESS / dtoj4700 Access
dtoj4700 Access
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了dtoj4700 Access,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1968字,纯文字阅读大概需要3分钟。
内容图文
![dtoj4700 Access](/upload/InfoBanner/zyjiaocheng/1273/d71323bd06d348a4b6fc77a0571ac344.jpg)
在一棵有根树中,边有两种:虚边和实边。一个点最多和一个儿子之间有实边。
当我们执行 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。
![技术分享图片](/img/jia.gif)
![技术分享图片](/img/jian.gif)
#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; }
原文:https://www.cnblogs.com/liankewei/p/12388281.html
内容总结
以上是互联网集市为您收集整理的dtoj4700 Access全部内容,希望文章能够帮你解决dtoj4700 Access所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。