iis 默认网站删除,网站开发者密钥,asp网站设计,黑龙江省建设安全网站来源#xff1a;牛客网#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;题目描述
“你#xff0c;你认错人了。我真的#xff0c;真的不是食人魔。”–蓝魔法师
给出一棵树#xff0c;求有多少种删边方案#xff0c;使得删后的图每个连通块大小小于等于k…来源牛客网 文章目录题目描述题解代码题目描述
“你你认错人了。我真的真的不是食人魔。”–蓝魔法师
给出一棵树求有多少种删边方案使得删后的图每个连通块大小小于等于k两种方案不同当且仅当存在一条边在一个方案中被删除而在另一个方案中未被删除答案对998244353取模 输入描述: 第一行两个整数n,k, 表示点数和限制 2 n 2000, 1 k 2000 接下来n-1行每行包括两个整数u,v表示u,v两点之间有一条无向边 保证初始图联通且合法 输出描述: 共一行一个整数表示方案数对998244353取模的结果 示例1 输入 复制
5 2
1 2
1 3
2 4
2 5输出 复制
7题解
以一号点为根树型dp求解 dp[u][x]表示u点连通块大小为x的方案数 考虑u的儿子v有两种选择 断开u–v这条边v的子树再怎么分对当前的x不存在影响了乘起来即可dp[u][x]dp[u][x] * sumv 如果不断开u–vu中大小为i的连通块与v中大小为j的连通块合成大小为ij的连通块 dp[u][ij]dp[u][i] * dp[v][x-i]
代码
#include cstdio
#include cstring
#include algorithm
#include iostream
#include vector
#include cmath
using namespace std;
typedef long long ll;
const ll mod998244353;
const int maxn200010;
vectorintG[maxn];
ll dp[maxn][maxn];
ll n,k;
ll temp[maxn];
ll size[maxn];//每个节点的子节点个数
void dfs(int u){size[u]1;dp[u][1]1;for(int i0;iG[u].size();i){int vG[u][i];dfs(v);memset(temp,0,sizeof(temp));for(int ii1;iisize[u];ii){for(int j0;jmin(k-ii,size[v]);j){temp[iij](temp[iij]%moddp[u][ii]*dp[v][j]%mod)%mod;}}for(int j1;jk;j){dp[u][j]temp[j];}size[u]size[v];}for(int i1;ik;i){dp[u][0]dp[u][i];dp[u][0]%mod;}
}int main(){while(scanf(%lld%lld,n,k)!EOF){for(int i1;in;i){int u,v;scanf(%d%d,u,v);G[u].push_back(v);}memset(dp,0,sizeof(dp));dfs(1);printf(%lld\n,dp[1][0]);}return 0;
}
