题意 给了n个点的数 每个点有一个w[i]权值，如果你选择了i这个点那么距离i这个点距离为w[i]的点将被除去，最后问 选则尽量少的点把这n个点全部删除
1<=n<=100000, 0<=w<=100，
down[i][j]表示以i为根节点的树 在他的子树中在距离他 j距离 范围内存在至少一个点没有被除去所选择的最少点数
up[i][j] 表示以i为根的树 他的子树全部都被除去，并且距离他为j的其他点可被除去 所选择的最小点数
考虑状态转移
如果第i个点不选
那么
j=0时
down[i][0]=sigma(up[v][0]){v为i的孩子}
up[i][0] =min(up[i][0], up[v][1]+down[i][0]-up[v][0]){v为i的孩子}
j!=0的时候
down[i][j]=down[i][j]+down[v][j-1](v为i的孩子)
up[i][j]=min(up[i][j],up[v][j+1]+down[i][j]-down[v][j-1]){v为i的孩子 ， 自然你也可以在他的孩子中在j范围内取更多的点，但是好好想想这样是没有必要的}
选了这个点
那么up[i][j]=min( up[i][j] , Sigma(G[v][w[i]-1]) ) {v为i的孩子，自然也可以选择更进的点 但是也是没有必要的 因为我们每次都更新了G[v][w[i]-1]的值 }
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;
const int maxn =+;
const int maxm=+;
int up[maxn][maxm],down[maxn][maxm],w[maxn];
vector<int>G[maxn];
int n;
void dfs(int cur, int per)
{
for(int i=; i<=; i++)up[cur][i]=n;
memset(down[cur],,sizeof(down[cur]));
int siz =G[cur].size();
int sum=;
for(int i=; i<siz; i++)
{
int to=G[cur][i];
if(to==per)continue;
dfs(to,cur);
if(w[cur]) sum+=down[to][w[cur]-];
else sum+=up[to][];
down[cur][]+=up[to][];
for(int j=; j<=; j++)
down[cur][j]+=down[to][j-];
}
for(int i=; i<siz; i++)
{
int to=G[cur][i];
if(to==per)continue;
up[cur][]=min(up[cur][],up[to][]+down[cur][]-up[to][]);
for(int j=; j<; j++)
up[cur][j]=min(up[cur][j],up[to][j+]+down[cur][j]-down[to][j-]);
}
for(int i=; i<=w[cur]; i++)up[cur][i]=min(up[cur][i],sum);
for(int i=; i>=;i--)up[cur][i]=min(up[cur][i],up[cur][i+]);
down[cur][]=min(down[cur][],up[cur][]);
for(int i=; i<=; i++)
down[cur][i]=min(down[cur][i],down[cur][i-]);
}
int main()
{
while(scanf("%d",&n)==)
{
for(int i=; i<=n; i++)
{
scanf("%d",&w[i]);
G[i].clear();
}
for(int i=; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
dfs(,);
int ans=n;
for(int i=; i<=; i++)ans=min(ans,up[][i]);
printf("%d\n",ans);
}
return ;
}