【日常小测】噫

链接

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/11/20161112.pdf (T2)
原版题解：http://oi.cyo.ng/?attachment_id=1904

题解

首先这个题目暴力的DP大家肯定都会
然而并不知道小火车是怎么优化到O(n^3)的…..

考虑暴力DP的限制：同时记录了最大值和最小值
但因为有d的限制，所以只要记录一个极值便可以推出另外一个

但直接扔掉一个极值并且按照原有的转移来转移的话，会丢掉一些情况
比如：从下到上，节点的权值递增的情况
于是考虑所有点在更新答案的时候，更新所有符合限制的上限
于是转移就可以做到O(1)辣！
接着，整体DP就成了O(n^2)辣！

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000+9;
const int M = N << 1;
const int MX = 5000;
const int INF = 100000000;

int head[N],nxt[M],to[M],val[N],f[N][N],g[N],n,d;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void solve(int w, int fa) {
	int lim = min(val[w]+d, MX);
	for (int i=val[w];i<=lim;i++)
		f[w][i] = 0;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != fa) {
			solve(to[i], w);
			for (int j=val[w];j<=lim;j++) 
				f[w][j] += min(g[to[i]], f[to[i]][j]);
		}
	}	
	for (int i=val[w];i<=lim;i++)
		g[w] = min(g[w], f[w][i] + 1);
}

int main(){
	freopen("yi.in","r",stdin);
	freopen("yi.out","w",stdout);
	memset(f,60,sizeof(f));
	memset(g,60,sizeof(g));
	d = read(); n = read();
	for (int i=1;i<=n;i++)
		val[i] = read();
	for (int i=1;i<n;i++)
		Add_Edge(read(), read());
	solve(1, 0);
	printf("%d\n",g[1]);
	return 0;
}