[文章目录]
Description
给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K，n<=40000
点分治裸题。第一道点分治。
对于树上的所有点进行点分治，分治经过该点的链和不经过该点的链，为了保证复杂度，每次需要找到一个伪重心，使得去掉该点，问题大小最少变成n/2。
对于这道题，统计出所有链的长度，然后排序，用两个指针扫一边数组就好了。
复杂度：T(n)=2T(n/2)+nlogn=>O(nlog2n)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 41000
int n,nn,k;
int head[N],to[N<<1],nxt[N<<1],data[N<<1],cnt;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
}
int root,siz[N],msi[N],vis[N],dis[N],cg[N],ans;
void getroot(int x,int pre)
{
siz[x]=1; msi[x]=0;
for(int i=head[x];i;i=nxt[i])
if(!vis[to[i]]&&to[i]!=pre)
{
getroot(to[i],x);
siz[x]+=siz[to[i]];
msi[x]=max(msi[x],siz[to[i]]);
}
msi[x]=max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void dfs(int x,int pre)
{
cg[++cg[0]]=dis[x];
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre&&!vis[to[i]])
{
dis[to[i]]=dis[x]+data[i];
dfs(to[i],x);
}
}
int calc(int x,int now)
{
dis[x]=now; cg[0]=0;
dfs(x,0);
sort(cg+1,cg+cg[0]+1);
int l=1,r=cg[0],re=0;
while(l<r)
{
if(cg[l]+cg[r]<=k) re+=r-l,++l;
else --r;
}
return re;
}
void solve(int x)
{
vis[x]=1; ans+=calc(x,0);
for(int i=head[x];i;i=nxt[i])
if(!vis[to[i]])
{
ans-=calc(to[i],data[i]);
nn=siz[to[i]]; root=0;
getroot(to[i],0);
solve(root);
}
}
int main()
{
scanf("%d",&n); int i,x,y,z;
for(i=1;i!=n;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
scanf("%d",&k);
nn=n; msi[0]=1<<30;
getroot(1,0);
solve(root);
printf("%d\n",ans);
return 0;
}