【DP】 cf 486D

1216 단어 dp
각 점을 가장 작은 값으로 고려...그리고
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int mod = 1000000007;
const int maxn = 2005;
const int maxm = 4005;

struct Edge
{
	int v;
	Edge *next;
}E[maxm], *H[maxn], *edges;

LL f[maxn];
int a[maxn];
int n, m;

void addedges(int u, int v)
{
	edges->v = v;
	edges->next = H[u];
	H[u] = edges++;
}

void init()
{
	edges = E;
	memset(H, 0, sizeof H);
}

void dfs(int u, int fa, int rt)
{
	f[u] = 1;
	for(Edge *e = H[u]; e; e = e->next) if(e->v != fa) {
		int v = e->v;
		if(a[v] < a[rt] || a[v] > a[rt] + m) continue;
		if(a[v] == a[rt] && v < rt) continue;
		dfs(v, u, rt);
		f[u] = f[u] * (f[v] + 1) % mod;
	}
}

void work()
{
	scanf("%d%d", &m, &n);
	
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		addedges(u, v);
		addedges(v, u);
	}
	
	LL ans = 0;
	for(int i = 1; i <= n; i++) {
		dfs(i, i, i);
		ans = (ans + f[i]) % mod;
	}
	printf("%I64d
", ans); } int main() { //freopen("data", "r", stdin); init(); work(); return 0; }

좋은 웹페이지 즐겨찾기