Solution of CF855C

· · 题解

Description

原题的翻译多少有点问题。搬一下 一扶苏一 在题解中的翻译：

给你一个树，可以染 m 个颜色，定义一个特殊颜色 k ， 要求保证整棵树上特殊颜色的个数不超过 x 个。同时，如果一个节点是特殊颜色，那么它的相邻节点的颜色编号必须全部小于 k。求方案数。

Analysis

读题意，树上方案数统计问题，显然树形 dp 。

考虑什么因素会对答案造成影响：子树内 已经染的特殊颜色数量，当前点编号 与特殊颜色编号的关系 。

与特殊编号的关系无非 3 种，小于，等于，大于，只要是这 3 种情况中的一种，具体的颜色不会对答案造成影响（例如 k=3 ，当前节点是 1/2 不影响答案）。

那么状态就很显然了。

设 f_{x,j,0/1/2} 表示在 x 的子树内已经取了 j 个特殊颜色，当前节点颜色编号 小于/等于/大于 k 的方案数。

接下来，就是一般的树形背包了。

根据题意，有状态转移方程：

（其中， x 表示当前节点， y 表示当前正在合并的子树， si_{i} 表示在以 i 为根的子树内点的数量。）

  1. 当前节点编号 < k ，那么儿子随便取：
f_{x,i+j,0}=\sum\limits_{i=0}^{si_{x}}\sum\limits_{j=0}^{si_{y}}f_{x,i,0}\times(f_{y,j,0}+f_{y,j,1}+f_{y,j,2})
  1. 当前节点编号 = k ，那么儿子编号 <k ：
f_{x,i+j,0}=\sum\limits_{i=0}^{si_{x}}\sum\limits_{j=0}^{si_{y}}f_{x,i,0}\times f_{y,j,0}
  1. 当前节点编号 > k ，那么儿子只有 k 不能取：
f_{x,i+j,0}=\sum\limits_{i=0}^{si_{x}}\sum\limits_{j=0}^{si_{y}}f_{x,i,0}\times (f_{y,j,0}+f_{y,j,2})

边界情况：

f_{x,0,0}=k-1 f_{x,1,1}=1 f_{x,0,2}=m-k

Notice

Code

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
inline LL read(){
    LL res=0,fl=1;
    char ch=getchar();
    while(!(ch>='0' && ch<='9')){if(ch=='-')fl=-1;ch=getchar();}
    while(ch>='0' && ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
    return res*fl;
}
inline LL max(LL a,LL b){return a>b?a:b;}
inline LL min(LL a,LL b){return a<b?a:b;}
inline void swap(int &a,int &b){int c;c=a;a=b;b=c;}
const int MAXN=1e5+5,MAXK=10+5,mod=1e9+7;
int n,m,k,p,ans=0,si[MAXN],f[MAXN][MAXK][3],g[MAXN][MAXK];
vector<int> e[MAXN];
inline void Tree_dp(int x,int fa){
    si[x]=1;
    f[x][0][0]=k-1;
    f[x][1][1]=1;
    f[x][0][2]=m-k;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y!=fa){
            Tree_dp(y,x);
            int up1=min(si[x],p),up2;
            for(int j=0;j<=up1;j++)
                for(int c=0;c<=2;c++)
                    g[j][c]=f[x][j][c],f[x][j][c]=0;

            for(int j=0;j<=up1;j++){
                up2=min(si[y],p-j);
                for(int l=0;l<=up2;l++){
                    f[x][j+l][0]=(f[x][j+l][0]+1LL*g[j][0]%mod*((f[y][l][0]+f[y][l][1])%mod+f[y][l][2])%mod)%mod;
                    f[x][j+l][1]=(f[x][j+l][1]+1LL*g[j][1]%mod*f[y][l][0]%mod)%mod;
                    f[x][j+l][2]=(f[x][j+l][2]+1LL*g[j][2]%mod*(f[y][l][0]+f[y][l][2])%mod)%mod;
                }
            }
            si[x]+=si[y];
        }
    }
}
int main() {
    int x,y;
    n=read(),m=read();
    for(int i=1;i<n;i++){
        x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    k=read(),p=read();
    Tree_dp(1,0);
    for(int i=0;i<=p;i++)
        for(int j=0;j<=2;j++)
            ans=(ans+f[1][i][j])%mod;
    cout<<ans<<'\n';
    return 0;
}