题意就是要求一棵树上的最长不下降序列，同时不下降序列的最小值与最大值不超过D。
做法是树分治+线段树，假设树根是x,y是其当前需要处理的子树，对于子树y，需要处理出两个数组MN,MX，MN[i]表示以x为第一个数字的不下降子序列中第i个数的最小值，MX[i]表示以x为第一个数字的不上升子序列中第i个数的最大值。如果当前子树有一个以x为首的不下降序列，那么我们就需要在之前处理的子树中找一条以x为首的满足约束条件不上升序列，可以用线段树来查询。同时每做完一颗子树的时候，用MN,MX对线段树进行更新。对于不经过x的情况可以递归下去处理。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000010
using namespace std;
int dp,p[N],s[N],pre[N],tt[N],flag[N],father[N],tmproot,n,d,ttt;
int i,v[N],a,b,mn,mx,MN[N],MX[N],U,V,ans;
int l[N],r[N],smn[N],smx[N],vsmn[N],vsmx[N];
void build(int x,int a,int b)
{
int m;
l[x]=a;r[x]=b;
if (x>ttt) ttt=x;
if (b-a>)
{
m=(a+b)>>;
build(*x,a,m);
build(*x+,m,b);
}
}
void clean(int x)
{
if (vsmn[x])
{
smn[x]=;
if (*x<=ttt)
vsmn[*x]=;
if (*x+<=ttt)
vsmn[*x+]=;
vsmn[x]=;
} if (vsmx[x])
{
smx[x]=;
if (*x<=ttt)
vsmx[*x]=;
if (*x+<=ttt)
vsmx[*x+]=;
vsmx[x]=;
}
}
void change(int x,int a,int b,int c,int typ)
{
int m;
clean(x);
if ((a<=l[x])&&(r[x]<=b))
{
if (typ==)
smn[x]=max(smn[x],c);
else
smx[x]=max(smx[x],c);
return;
}
m=(l[x]+r[x])>>;
if (a<m) change(*x,a,b,c,typ);
if (m<b) change(*x+,a,b,c,typ);
clean(*x);clean(*x+);
if (!typ)
smn[x]=max(smn[*x],smn[*x+]);
else
smx[x]=max(smx[*x],smx[*x+]);
}
int query(int x,int a,int b,int typ)
{
int m,ans=;
clean(x);
if ((a<=l[x]&&(r[x]<=b)))
{
if (typ==)
return smn[x];
else
return smx[x];
}
m=(l[x]+r[x])>>;
if (a<m) ans=max(ans,query(*x,a,b,typ));
if (m<b) ans=max(ans,query(*x+,a,b,typ));
return ans;
}
void link(int x,int y)
{
dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;
}
int getroot(int x,int fa,int sum)
{
int i,f=;
i=p[x];
father[x]=fa;
s[x]=;
while (i)
{
if ((tt[i]!=fa)&&(!flag[tt[i]]))
{
getroot(tt[i],x,sum);
s[x]=s[x]+s[tt[i]];
if (s[tt[i]]>sum/) f=;
}
i=pre[i];
}
if (sum-s[x]>sum/) f=;
if (!f) tmproot=x;
}
void dfs(int x,int fa,int mn,int mx)
{
int i;
i=p[x];
if (v[x]>=v[fa])
{
if (mn)
{
mn++;
MN[mn]=min(MN[mn],v[x]);
}
if (v[x]>v[fa])
mx=;
}
if (v[x]<=v[fa])
{
if (mx)
{
mx++;
MX[mx]=max(MX[mx],v[x]);
}
if (v[x]<v[fa])
mn=;
}
U=max(U,mn);
V=max(V,mx);
while (i)
{
if ((tt[i]!=fa)&&(!flag[tt[i]]))
dfs(tt[i],x,mn,mx);
i=pre[i];
}
}
void work(int x,int sum)
{
int i,j,k,root;
getroot(x,,sum);
root=tmproot;
i=p[root];
flag[root]=;
while (i)
{
if (flag[tt[i]]==)
{
if (tt[i]==father[root])
work(tt[i],sum-s[root]);
else
work(tt[i],s[tt[i]]);
}
i=pre[i];
}
//------------------------------
i=p[root];
vsmn[]=;
vsmx[]=;
while (i)
{
if (!flag[tt[i]])
{
for (j=;j<=U;j++)
MN[j]=0x37373737;
for (j=;j<=V;j++)
MX[j]=;
U=;V=;
dfs(tt[i],root,,);
for (j=;j<=U;j++)
{
if (MN[j]-d<=v[root])
ans=max(ans,j);
k=MN[j]-d;
if (k<) k=;
if (k<=v[root])
ans=max(ans,j+query(,k-,v[root],)-);
}
for (j=;j<=V;j++)
{
if (MX[j]+d>=v[root])
ans=max(ans,j);
k=MX[j]+d;
if (k>) k=;
if (k>=v[root])
ans=max(ans,j+query(,v[root]-,k,)-);
} for (j=;j<=U;j++)
change(,MN[j]-,MN[j],j,);
for (j=;j<=V;j++)
change(,MX[j]-,MX[j],j,);
}
i=pre[i];
}
flag[root]=;
}
int main()
{
build(,,);
for (i=;i<=;i++)
MN[i]=0x37373737;
int test,ii=;
scanf("%d",&test);
while (test)
{
test--;
ii++;
dp=;memset(p,,sizeof(p));
scanf("%d%d",&n,&d);
for (i=;i<=n;i++)
scanf("%d",&v[i]);
for (i=;i<=n-;i++)
{
scanf("%d%d",&a,&b);
link(a,b);
link(b,a);
}
ans=;
work(,n);
printf("Case #%d: %d\n",ii,ans);
}
}