蓝魔法师(树形DP)
程序员文章站
2022-03-13 17:19:35
...
思路:树上求方案,dp[i][j]表示以i的子树里连通块个数为j的方案数(j<=k)这里我们有2个选择,
1.删除当前边,此时节点u与他的的子节点v所能构成的方案数就是dp[u][x]乘上dp[v][1——x]
2.不删除当前边,此时节点u与节点v构成i+j(i为u的连通块个数,j为v的连通块个数)个连通块转移方程是,这里我们需要用sz[u]记录一下u节点的子节点个数,i+j<=k && i<=min(sz[u],k) j<=min(sz[v],k),最后遍历一累加dp[1][1——k]就是答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=998244353;
const int N=2e6+10;
const int M=2e3+10;
const int inf=0x7f7f7f7f;
const int maxx=2e5+7;
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a*(b/gcd(a,b));
}
template <class T>
void read(T &x)
{
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-')
op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op)
x = -x;
}
template <class T>
void write(T x)
{
if(x < 0)
x = -x, putchar('-');
if(x >= 10)
write(x / 10);
putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
ll res=1%p;
while(b)
{
if(b&1) res=res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
struct node
{
int v,nex;
}edge[N];
int cnt=0,head[2020];
ll sz[2020];
ll dp[2020][2020];
ll n,k;
void add(int u,int v)
{
edge[++cnt].v=v;
edge[cnt].nex=head[u];
head[u]=cnt;
}
void dfs(int u,int fa)
{
dp[u][1]=sz[u]=1;
for(int i=head[u];~i;i=edge[i].nex)
{
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u);
ll sum=0;
for(int j=1;j<=min(sz[v],k);j++)
{
sum=(sum+dp[v][j])%mod;
}
for(int j=min(k,sz[u]);j;j--)
{
for(int p=min(k,sz[v]);p;p--)
{
if(j+p<=k) dp[u][j+p]=(dp[u][j+p]+dp[u][j]*dp[v][p])%mod;//不删边
}
dp[u][j]=dp[u][j]*sum%mod;//删除这个边
}
sz[u]+=sz[v];
}
}
int main()
{
SIS;
cin>>n>>k;
memset(head,-1,sizeof head);
for(int i=0;i<n-1;i++)
{
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs(1,0);
ll ans=0;
for(int i=1;i<=k;i++)
ans=(ans+dp[1][i])%mod;
cout<<ans<<endl;
return 0;
}
推荐阅读
-
树形DP求树的直径
-
HDU2196 Computer(树形DP)
-
BZOJ2286: [Sdoi2011]消耗战(虚树/树形DP)
-
TopcoderSRM679 Div1 250 FiringEmployees(树形dp)
-
cf633F. The Chocolate Spree(树形dp)
-
BZOJ1722: [Usaco2006 Mar] Milk Team Select 产奶比赛(树形dp)
-
洛谷P2607 [ZJOI2008]骑士(树形dp)
-
BZOJ1060: [ZJOI2007]时态同步(树形dp 贪心)
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)