点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp：0922T4

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133217931

首先连通块，所以点分治肯定是

Trick1 钦定选根的连通块dp

对于钦定选根的连通块dp，有一种常见思路

先对原树求其dfn序，按dfn序 倒序 求解

具体的，对于当前点 ii （注意这里都是指dfn序），我们可以钦定 ii 是否选

如果 ii 选，就由 i+1i+1 ，也就是 ii 的第一个儿子转移过来（因为只有他选他子树才可能被选）

如果 ii 不选，就由 i+wii+w_i 转移过来，因为他的儿子必然不会被选

至于 ii 和 i+wii+w_i 同时选的情况，我们在 i+1i+1 那里已经算了

对于 ii 和 i+wii+w_i 是否连通的问题，当他们的lca都被选时，则他们必然也被选，这里一定会在他们祖先那里被算到

在这里插入图片描述

Trick 2 对于乘积类dp的根号优化方法

考虑直接 dp[x][i]dp[x][i] ， ii 值域过大。

但我们可以拆分 f(x,i),g(x,i)f(x,i),g(x,i) ，代表已选乘积为 ii / 还可以选乘积为 ii 的方案数

这样状态直接压成 O(m)O(\sqrt m)

其实也可以用整除分块的证明进行预处理

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 4010
#define M 1510
#define mo (int)(1e9+7)
int n, m, i, j, k, T;
int Rt, rt, f[N][M], g[N][M]; 
int mx[N], w[N], dfn[N], tot, sum,  u, v; 
int sq, p[N], v1, v2, a[N], ans; 
vector<int>G[N]; 

void dfs(int x, int fa) {
	w[x]=mx[x]=1; 
	for(int y : G[x]) {
		if(y==fa || p[y]) continue; 
		dfs(y, x); 
		w[x]+=w[y]; 
		mx[x]=max(mx[x], w[y]); 
	}
	mx[x]=max(mx[x], sum-w[x]); 
	if(mx[x]<mx[rt]) rt=x; 
}

void dfs2(int x, int fa) {
	dfn[++tot]=x;  
	for(int y: G[x]) 
		if(y!=fa && !p[y]) dfs2(y, x); 
}

void Add(int &a, int b) {
	a=(a+b)%mo; 
}

void dfz(int x) {
//	printf("> %lld\n", x); 
	int i, j, u; 
	tot=0; dfs(x, 0); dfs2(x, 0); 
//	for(i=1; i<=tot; ++i) printf("%lld ", dfn[i]); printf("\n"); 
	for(i=0; i<=tot+5; ++i)
		for(j=0; j<=sq+5; ++j) f[i][j]=g[i][j]=0; 
//	f[tot+1][1]=1; 
	
	for(i=tot; i>=1; --i) {
		u=dfn[i]; 
		if(a[u]>sq) Add(g[i][m/a[u]], 1); 
		else Add(f[i][a[u]], 1); 
		for(j=1; j<=sq; ++j) {
			v1=i+1; v2=i+w[u]; 
			if(j*a[u]>sq && j*a[u]<=m) Add(g[i][m/(j*a[u])], f[v1][j]); 
			else if(j*a[u]<=m) Add(f[i][j*a[u]], f[v1][j]); 
			if(j>=a[u]) Add(g[i][j/a[u]], g[v1][j]); 
//			
//			
//			
			Add(f[i][j], f[v2][j]); Add(g[i][j], g[v2][j]); 
		}
	}
	for(i=1; i<=sq; ++i) Add(ans, f[1][i]+g[1][i]); 
	
	
	
//	printf("# %lld : %lld\n", x, ans); 
	
	dfs(x, 0); p[x]=1; 
	for(int y : G[x]) 
		if(!p[y]) {
			dfs(y, x); 
			sum=w[y]; 
			mx[rt=0]=1e9; 
			dfs(y, x); 
			dfz(rt); 
		}
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
		freopen("fn.in", "r", stdin);
	freopen("fn.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); sq=sqrt(m); 
//	printf("# %lld\n", sq); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(i=1; i<n; ++i) {
		u=read(); v=read(); 
		G[u].pb(v); G[v].pb(u); 
	}
	sum=n; mx[rt=0]=1e9; 
	dfs(1, 0); Rt=rt; 
//	printf("%lld\n", rt); 
	dfz(rt);
	printf("%lld", (ans%mo+mo)%mo); 
	return 0;
}