cf855C Helga Hufflepuff's Cup(dp)

855C

题意

给一棵树($n\leq 10^5$),要求你计算,有多少种方法对树赋上权值,使得树上恰好有$x$个点权值为$k$,并且对于权值为$k$的点它的周围相邻的点权值小于它。

样例

sample1

1
2
3
4
5
4 2
1 2
2 3
1 4
1 2
1
1

sample2

1
2
3
4
3 3
1 2
1 3
2 1
1
13

题解

和一般的div2C比起来还是偏难一点的…

考虑在树上$dp$,由于每个点对周围相邻点的影响只有

  • 这个点权值为$k$,那么他可以作为一个权值为$k$的点
  • 这个点权值小于$k$,那么他可以作为一个权值为$k$的点的邻居
  • 这个点权值可以乱取只要不等于$k$,那么他可以作为一堆乱取的但不是$k$的点的邻居

边界情况是叶子结点的计数方案是确定的,于是考虑从下往上$dp$,每次$dp$影响的主要因素还有现在权值为$k$的点有几个,记$dp[v][i][0/1/2]$表示

  • $dp[v][i][0]$这个点权值等于$k$,它的子树一共有$i$个点权值等于$k$
  • $dp[v][i][1]$这个点权值小于$k$,它的子树一共有$i$个点权值等于$k$
  • $dp[v][i][2]$这个点权值大于或小于$k$,它的子树一共有$i$个点权值等于$k$

考虑每个结点的直接儿子,这个结点的本身取值和直接的儿子息息相关。设置一个辅助数组$g[cnt][i][0/1/2]$,表示到了第$cnt$个儿子,它的另两维状态和$dp$一样。

那么更新时就会有:
$g[cnt][i][0]=\sum_{j=0}^{i} g[cnt-1][j][0] \times dp[v][i-j][1]$

$g[cnt][i][1]=\sum_{j=0}^{i} g[cnt-1][j][1] \times (dp[v][i-j][0]+dp[v][i-j][2])$

$g[cnt][i][2]=\sum_{j=0}^{i} g[cnt-1][j][2] \times dp[v][i-j][2]$

设子树总数为$Cnt$则有

$dp[v][i][1]=g[Cnt][i][1] \times (k-1)$

$dp[v][i][2]=g[Cnt][i][2]\times (m-k) +dp[v][i][1]$

$dp[v][i][0]=g[Cnt][i-1][0]$

然而实际上我们记下$cnt$这一维并没有卵用因为这一维仅仅只是象征到达了第几个子树,对最后的答案没有影响。所以真正更新时用中间变量过渡一下就好了。

复杂度

$\mathcal O(n)$

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
const int maxX=10+5;
vector<int > G[maxn];
int n,m,k,x;
typedef long long ll;
const ll mo=(ll)1e9+7;
ll dp[maxn][maxX][3];
void dfs(int u,int fa)
{
dp[u][0][0]=dp[u][0][1]=dp[u][0][2]=1;
//这里实质上是g[0][0][0]=g[0][0][1]=g[0][0][2]=1
//即任何子树都没有遍历到的时候总是有一种方案的。
for(int z=(int)G[u].size()-1;z>=0;--z){
int v=G[u][z];
if(v!=fa){
dfs(v,u);
for(int i=x;i>=0;i--){
ll a=0,b=0,c=0;
for(int j=0;j<=i;j++){
a=(a+dp[u][j][0]*dp[v][i-j][1])%mo;
b=(b+dp[u][j][1]*(dp[v][i-j][0]+dp[v][i-j][2])%mo)%mo;
c=(c+dp[u][j][2]*dp[v][i-j][2])%mo;
}
dp[u][i][0]=a;
dp[u][i][1]=b;
dp[u][i][2]=c;
}
}
}
for(int i=x;~i;i--){
dp[u][i][1]=(dp[u][i][1]*(ll)(k-1))%mo;
dp[u][i][2]=((dp[u][i][2]*(ll)(m-k))%mo+dp[u][i][1])%mo;
dp[u][i][0]=i>0?dp[u][i-1][0]:0;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++){
int v,u;
scanf("%d%d",&v,&u);
G[v].push_back(u);
G[u].push_back(v);
}
scanf("%d%d",&k,&x);
dfs(1,-1);
ll Ans=0;
for(int i=0;i<=x;i++){
Ans=(0ll+Ans+dp[1][i][0])%mo;
Ans=(0ll+Ans+dp[1][i][2])%mo;
}
printf("%lld\n",Ans);
return 0;
}