欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝魔法师(树形DP)

程序员文章站 2022-03-13 17:19:35
...

蓝魔法师(树形DP)

思路:树上求方案,dp[i][j]表示以i的子树里连通块个数为j的方案数(j<=k)这里我们有2个选择,

1.删除当前边,此时节点u与他的的子节点v所能构成的方案数就是dp[u][x]乘上dp[v][1——x]

dp[u][x]=dp[u][x]i=1xdp[v][i]dp[u][x]= dp[u][x]*\sum_{i=1}^xdp[v][i]

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]就是答案。

dp[u][i+j]+=dp[u][i]dp[v][j]dp[u][i+j]+=dp[u][i]*dp[v][j]

#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 牛客