我们考虑忽略贡献直接计数怎么做？

可以发现题目要求即为一个点为一个划分集合的根，其他的点其每一个子树内只存在一个。

显然考虑动态规划。

考虑到我们只在乎一个子树中有多少个点没有加入划分集合，$dp(u,i)$ 表示 $u$ 的子树内剩余 $i$ 个点。

转移分为以这个点为根划分以及不划分两种。

  • $dp(u,i) \cdot dp(v,j) \to dp(u,i+j)$
  • $dp(u,i) \cdot dp(v,j) \cdot j \to dp(u,i+j-1)$

然后考虑如何计算贡献，拆开考察组合意义，即：每一个划分中选择一个点（下文称黑点）的所有方案的乘积和。

于是考虑 $dp(u,i,j)$ 表示 $u$ 的子树中，$i$ 个未划分的白点，$j$ 个未划分的黑点的总贡献。

分三类考虑，$u$ 不划分，$u$ 为黑色点并划分，$u$ 为白色点并划分。

不划分的点我们也需要先钦定颜色。

具体来说维护三个转移数组：$f$,$g$,$h$，分别表示不划分，每一个子树选一个白点划分或不选，其中有一个子树选了一个黑点，其他选白点或不选的方案

遍历每一个棵子树，其可以不选，选一个白点，选一个黑点，按照逻辑转移即可，注意选白点或黑点有一个权值。

最后将转移数组合并到 $dp$，$f$ 需要考虑 $u$ 的颜色（被别人选），$g$ 则 $u$ 选黑色，注意 $a(u)$ 的权值，$h$ 则 $u$ 选白色并划分。

时间复杂度 $O(n^4)$。

具体方程见代码：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int n,mod;
int a[maxn+5];
vector<int> E[maxn+5];
int sz[maxn+5];
int dp[maxn+5][maxn+5][maxn+5];
int f[2][maxn+5][maxn+5][maxn+5];
int g[2][maxn+5][maxn+5][maxn+5];
int h[2][maxn+5][maxn+5][maxn+5];
inline void Add(int &x,int y){
    if(x+y>=mod) x=x+y-mod;
    else x=x+y;
}
void Dfs(int u,int fa){
    for(int v:E[u]) if(v!=fa) Dfs(v,u);
    f[0][u][0][0]=g[0][u][0][0]=1;
    for(int v:E[u]){
        if(v==fa) continue;
        for(int i=0;i<=sz[u];i++){
            for(int j=0;i+j<=sz[u];j++){
                for(int ii=0;ii<=sz[v];ii++){
                    for(int jj=0;ii+jj<=sz[v];jj++){
                        const int val=dp[v][ii][jj];
                        const int fval=f[0][u][i][j];
                        const int gval=g[0][u][i][j];
                        const int hval=h[0][u][i][j];
                        Add(f[1][u][i+ii][j+jj],1ll*fval*val%mod);
                        // Add(g[1][u][i+ii-1][j+jj],1ll*fval*val%mod*ii%mod);
                        if(i+ii) Add(g[1][u][i+ii-1][j+jj],1ll*gval*val%mod*ii%mod);
                        Add(g[1][u][i+ii][j+jj],1ll*gval*val%mod);
                        // Add(h[1][u][i+ii][j+jj-1],1ll*fval*val%mod*jj%mod);
                        if(j+jj) Add(h[1][u][i+ii][j+jj-1],1ll*gval*val%mod*jj%mod);
                        Add(h[1][u][i+ii][j+jj],1ll*hval*val%mod);
                        if(i+ii) Add(h[1][u][i+ii-1][j+jj],1ll*hval*val%mod*ii%mod);
                    }
                }
            }
        }
        sz[u]+=sz[v];
        swap(f[0][u],f[1][u]);
        memset(f[1][u],0,sizeof(f[1][u]));
        swap(g[0][u],g[1][u]);
        memset(g[1][u],0,sizeof(g[1][u]));
        swap(h[0][u],h[1][u]);
        memset(h[1][u],0,sizeof(h[1][u]));
    }
    for(int i=0;i<=sz[u];i++){
        for(int j=0;i+j<=sz[u];j++){
            Add(dp[u][i+1][j],f[0][u][i][j]);
            Add(dp[u][i][j+1],1ll*a[u]*f[0][u][i][j]%mod);
            Add(dp[u][i][j],1ll*a[u]*g[0][u][i][j]%mod);
            Add(dp[u][i][j],h[0][u][i][j]);
        }
    }
    sz[u]++;
}
signed main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    // freopen("ex_tree2.in","r",stdin);
    scanf("%d%d",&n,&mod);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }
    Dfs(1,0);
    printf("%d",dp[1][0][0]);
    return 0;
}