Vexoben
Dec 19, 2017
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5314
题意
给定一颗树，每个点有点权，求有多少个点对(u,v)满足u到v的路径中点权最大值与最小值之差不大于D
被题意杀了一天……
一开始以为(u,v)和(v,u)算一种，(u,u)也算一种方案，样例过了结果wa了一天。实际上是前者算两种后者不算
题解
应该是一个很裸的点分治+二维偏序吧
统计答案是记录分治中心到每个点的最大最小值，然后相当于对于每个点（mini,maxi）统计有多少个点对j满足（minj >= mini , maxj<=mini+d , minj >=maxi-d）
离线一下，关于min从大到小排序树状数组弄弄就好了
感觉点分治，二维偏序，离散化这三个算法都不是很熟。就当贴个模板吧
#pragma GCC optimize(3)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int T,n,d,num,cnt,tot,dif,root,maxsize;
int v[N<<1],val[N],use[N],siz[N],fir[N],arr[N<<1],nex[N<<1],tree[N<<1];
pair<int,int> pnt[N];
LL ans;
bool cmp(pair<int,int> &x,pair<int,int> &y) {
if (x.first!=y.first) return x.first>y.first;
return x.second>y.second;
}
inline void read(int &x) {
x=0; register char c=getchar();
while (c>'9'||c<'0') c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}
inline void Add_Edge(int x,int y) {
nex[++cnt]=fir[x];
fir[x]=cnt;
arr[cnt]=y;
}
inline int GetNum(int x) {
if (x<v[1]) return 0;
return lower_bound(v+1,v+dif+1,x+1)-v-1;
}
inline void Updata(int x,int del) {
for (;x<=dif;x+=x&-x) tree[x]+=del;
}
inline int Query(int x) {
register int ans=0;
for (;x;x-=x&-x) ans+=tree[x];
return ans;
}
inline void FindRoot(int x,int fa) {
siz[x]=1; int ms=0;
for (int i=fir[x];i;i=nex[i])
if (!use[arr[i]]&&arr[i]!=fa) {
FindRoot(arr[i],x);
siz[x]+=siz[arr[i]];
ms=max(ms,siz[arr[i]]);
}
if (max(ms,tot-siz[x])<maxsize) {
maxsize=max(ms,tot-ms);
root=x;
}
}
inline void dfs(int x,int fa,int minx,int maxx) {
minx=min(minx,val[x]);
maxx=max(maxx,val[x]);
pnt[++num]=make_pair(minx,maxx);
for (int i=fir[x];i;i=nex[i])
if (arr[i]!=fa&&!use[arr[i]])
dfs(arr[i],x,minx,maxx);
}
inline void Disperse() {
for (int i=1;i<=num;i++) {
v[++dif]=pnt[i].first;
v[++dif]=pnt[i].second;
}
sort(v+1,v+dif+1);
dif=unique(v+1,v+dif+1)-v-1;
}
inline LL Calc(int x,int cost) {
num=0; dif=0;
if (~cost) dfs(x,0,cost,cost);
else dfs(x,0,inf,0);
sort(pnt+1,pnt+num+1,cmp);
Disperse();
LL ax=0;
memset(tree,0,sizeof(int)*(dif+5));
for (int i=1;i<=num;i++)
if (pnt[i].second-pnt[i].first<=d) {
int t;
t=GetNum(pnt[i].first+d);
ax+=Query(t);
t=GetNum(pnt[i].second-d-1);
if (t>0) ax-=Query(t);
t=GetNum(pnt[i].second);
Updata(t,1);
}
return ax<<1;
}
inline void Solve(int x) {
use[x]=1;
ans+=Calc(x,-1);
for (int i=fir[x];i;i=nex[i]) {
if (!use[arr[i]]) {
tot=siz[arr[i]];
ans-=Calc(arr[i],val[x]);
maxsize=inf;
FindRoot(arr[i],x);
Solve(root);
}
}
}
inline void Work() {
cnt=0;
read(n); read(d);
memset(use,0,sizeof(int)*(n+5));
memset(fir,0,sizeof(int)*(n+5));
for (int i=1;i<=n;i++) read(val[i]),val[i]++;
for (int i=1;i<n;i++) {
int u,v;
read(u); read(v);
Add_Edge(u,v); Add_Edge(v,u);
}
tot=n; maxsize=inf;
FindRoot(1,0);
ans=0;
Solve(root);
printf("%lld\n",ans);
memset(tree,0,sizeof(int)*(n+5));
n=d=num=cnt=tot=dif=root=maxsize=0;
}
signed main() {
read(T);
while (T--) Work();
return 0;
}