点分治
- 求树内距离小于等于m的点对数
- 两个点均在某棵子树内
- 一个点在重心
- 两个点属于两棵子树
cpp
int n,m;
vector<PII> adj[N];
bool st[N];
int q[N],p[N];
int get_size(int u,int fa){//获取子树大小
if(st[u])return 0;
int res=1;
for(auto [v,w]:adj[u]){
if(v==fa)continue;
res+=get_size(v,u);
}
return res;
}
int get_wc(int u,int fa,int tot,int &wc){//获取重心(不一定是真重心，满足<=n/2即可)
if(st[u])return 0;
int sum=1,ms=0;
for(auto [v,w]:adj[u]){
if(v==fa)continue;
int t=get_wc(v,u,tot,wc);
ms=max(ms,t);
sum+=t;
}
ms=max(ms,tot-sum);
if(ms<=tot/2)wc=u;
return sum;
}
void get_dist(int u,int fa,int dis,int &qt){//获取子树全部dis
if(st[u])return;
q[qt++]=dis;
for(auto [v,w]:adj[u]){
if(v==fa)continue;
get_dist(v,u,dis+w,qt);
}
}
int get(int a[],int k){//计算
sort(a,a+k);
int res=0;
for(int i=k-1,j=-1;i>=0;i--){
while(j+1<i&&a[j+1]+a[i]<=m)j++;
j=min(j,i-1);
res+=j+1;
}
return res;
}
int cal(int u){
if(st[u])return 0;
int res=0;
get_wc(u,0,get_size(u,0),u);
st[u]=true;
int pt=0;
for(auto [v,w]:adj[u]){
int qt=0;
get_dist(v,0,w,qt);
res-=get(q,qt);//容斥，减去两个点在同一颗子树的情况
for(int k=0;k<qt;k++){
if(q[k]<=m)res++;//重心与子树的点
p[pt++]=q[k];
}
}
res+=get(p,pt);//总计算
for(auto [v,w]:adj[u])res+=cal(v);
return res;
}
void solve(){
cin>>n;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
cin>>m;
cout<<cal(1);
}