题目链接：hdu_5314_Happy King
题意：
给出一颗n个结点的树，点上有权值；
求点对(x,y)满足x!=y且x到y的路径上最大值与最小值的差<=D；
题解：
还是树的点分治，在统计答案的时候先按到根的最小值排序，然后用最大值减D去找有多少个满足答案。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
const int N=1e5+; int n,k,g[N],v[N*],nxt[N*],ed,w[N],t;
int vis[N],size[N],mx[N],mi,tot,root;
P dis[N];
ll ret; inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
void init(){F(i,,n)g[i]=,vis[i]=;ed=,ret=;} void dfs_size(int u,int fa)
{
size[u]=,mx[u]=;
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
{
dfs_size(v[i],u),size[u]+=size[v[i]];
if(size[v[i]]>mx[u])mx[u]=size[v[i]];
}
} void dfs_root(int r,int u,int fa)
{
if(size[r]-size[u]>mx[u])mx[u]=size[r]-size[u];
if(mx[u]<mi)mi=mx[u],root=u;
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
dfs_root(r,v[i],u);
} void dfs_dis(int u,int mi,int mx,int fa)
{
mi=min(mi,w[u]),mx=max(mx,w[u]);
if(mx<=mi+k)dis[++tot]=P(mi,mx);
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
dfs_dis(v[i],mi,mx,u);
} ll calc(int u,int mi,int mx)
{
ll ans=;
tot=,dfs_dis(u,mi,mx,);
sort(dis+,dis+tot+);
F(i,,tot)
{
int p=lower_bound(dis+,dis+i+,P(dis[i].second-k,))-dis;
ans+=i-p;
}
return ans;
} void dfs(int u=)
{
mi=n,dfs_size(u,);
dfs_root(u,u,);
ret+=calc(root,w[root],w[root]),vis[root]=;
for(int i=g[root];i;i=nxt[i])
if(!vis[v[i]])ret-=calc(v[i],w[root],w[root]);
for(int i=g[root];i;i=nxt[i])
if(!vis[v[i]])dfs(v[i]);
} int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
init();
F(i,,n)scanf("%d",w+i);
F(i,,n-)
{
int x,y;
scanf("%d%d",&x,&y);
adg(x,y),adg(y,x);
}
dfs(),printf("%lld\n",ret*);
}
return ;
}
法2：
将统计的答案按倒根的最大值排序，如果当前最大值为这个点的最大值，那么我们就在树状数组中去找最大值-D的答案，所以我们在统计好后需要将这个点的最小值插入树状数组
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
const int N=1e5+; int n,k,g[N],v[N*],nxt[N*],ed,w[N],t,hsh[N],hsh_ed;
int vis[N],size[N],mx[N],mi,tot,root,sum[N];
P dis[N];ll ans; inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
void init(){F(i,,n)g[i]=,vis[i]=;ed=ans=,hsh_ed=;} inline void add(int x,int c){while(x<=hsh_ed+)sum[x]+=c,x+=x&-x;}
inline int ask(int x){int an=;while(x>)an+=sum[x],x-=x&-x;return an;}
inline int getid(int x){return lower_bound(hsh+,hsh++hsh_ed,x)-hsh;}
void dfs_size(int u,int fa)
{
size[u]=,mx[u]=;
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
{
dfs_size(v[i],u),size[u]+=size[v[i]];
if(size[v[i]]>mx[u])mx[u]=size[v[i]];
}
} void dfs_root(int r,int u,int fa)
{
if(size[r]-size[u]>mx[u])mx[u]=size[r]-size[u];
if(mx[u]<mi)mi=mx[u],root=u;
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
dfs_root(r,v[i],u);
} void dfs_dis(int u,int mi,int mx,int fa)
{
mi=min(mi,w[u]),mx=max(mx,w[u]);
if(mx<=mi+k)dis[++tot]=P(mx,mi);
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
dfs_dis(v[i],mi,mx,u);
} ll calc(int u,int mi,int mx)
{
ll ans=;
tot=,dfs_dis(u,mi,mx,);
sort(dis+,dis++tot);
F(i,,tot)
{
ans+=ask(hsh_ed)-ask(getid(dis[i].first-k)-);
add(getid(dis[i].second),);
}
F(i,,tot)add(getid(dis[i].second),-);
return ans;
} void dfs(int u=)
{
mi=n,dfs_size(u,);
dfs_root(u,u,);
ans+=calc(root,w[root],w[root]),vis[root]=;
for(int i=g[root];i;i=nxt[i])
if(!vis[v[i]])
ans-=calc(v[i],w[root],w[root]);
for(int i=g[root];i;i=nxt[i])
if(!vis[v[i]])dfs(v[i]);
} int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
init();
F(i,,n)scanf("%d",w+i),hsh[i]=w[i];
F(i,,n-)
{
int x,y;
scanf("%d%d",&x,&y);
adg(x,y),adg(y,x);
}
sort(hsh+,hsh++n),hsh_ed=unique(hsh+,hsh++n)-hsh;
dfs(),printf("%lld\n",ans*);
}
return ;
}