点分治作用（目前只知道这个）：
求一棵树上满足条件的节点二元组(u,v)个数，比较典型的是求dis(u,v)（dis表示距离）满足条件的(u,v)个数。
算了自己懒得写了，安利几个blog吧：
https://www.cnblogs.com/LadyLex/p/8006488.html
https://blog.csdn.net/qq_39553725/article/details/77542223
https://blog.csdn.net/zzkksunboy/article/details/70244945
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
#define MAXN 200010
#define INF 100000000
using namespace std;
struct edge
{
int u,v,w,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define w(x) ed[x].w
#define n(x) ed[x].nxt
}ed[MAXN*2];
int first[MAXN],num_e;
#define f(x) first[x]
int sum,mn,root;
int siz[MAXN],mxsiz[MAXN];
bool v[MAXN];
int n,k;
int ans=INF,t[1000010];
int dis[MAXN],dep[MAXN];
void getroot(int x,int fa)//查找根节点，没什么可说的。
{
siz[x]=1,mxsiz[x]=0;
for(int i=f(x);i;i=n(i))
if(!v[v(i)]&&v(i)!=fa)
{
getroot(v(i),x);
siz[x]+=siz[v(i)];
mxsiz[x]=max(siz[v(i)],mxsiz[x]);
}
mxsiz[x]=max(mxsiz[x],sum-siz[x]);
if(mxsiz[x]<mn)mn=mxsiz[x],root=x;
}
void cal(int x,int fa)//更新答案
{
if(dis[x]<=k)ans=min(ans,dep[x]+t[k-dis[x]]);
for(int i=f(x);i;i=n(i))
if(!v[v(i)]&&v(i)!=fa)
{
dep[v(i)]=dep[x]+1;
dis[v(i)]=dis[x]+w(i);
cal(v(i),x);
}
}
int add(int x,int fa,int flag)//更新桶
{
if(dis[x]<=k)
{
if(flag)t[dis[x]]=min(t[dis[x]],dep[x]);
else t[dis[x]]=INF;
}
for(int i=f(x);i;i=n(i))
if(v(i)!=fa&&!v[v(i)])
add(v(i),x,flag);
}
void divide(int x)
{
v[x]=1;t[0]=0;
for(int i=f(x);i;i=n(i))
if(!v[v(i)])
{
dep[v(i)]=1,dis[v(i)]=w(i);
cal(v(i),0);//先用这个儿子更新答案，因为更新答案时要用到之前的儿子的信息，有点类似树p。
add(v(i),0,1);//先用这个儿子更新答案，再将这个儿子合并，确保不会出错。
}
for(int i=f(x);i;i=n(i))
if(!v[v(i)])
add(v(i),0,0);//清空桶。
for(int i=f(x);i;i=n(i))
if(!v[v(i)])
{
sum=siz[v(i)],mn=INF;
getroot(v(i),0);
divide(root);//分治树递归。
}
}
inline void adde(int u,int v,int w);
signed main()
{
// freopen("in.txt","r",stdin);
// freopen("1.in","r",stdin); scanf("%lld%lld",&n,&k);
int u,v,w;
for(int i=1;i<n;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
u++,v++;
adde(u,v,w),adde(v,u,w);
}
memset(t,0x7f,sizeof(t));
sum=n,mn=INF;
getroot(1,0);
divide(root);
if(ans==INF)puts("-1");
else printf("%lld\n",ans);
}
inline void adde(int u,int v,int w)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
w(num_e)=w;
n(num_e)=f(u);
f(u)=num_e;
}