【点分治】bzoj1468 Tree

同poj1741。

换了个更快的姿势，不会重复统计然后再减掉什么的啦~

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXN 40001

#define INF 2147483647

typedef pair<int,int> Point;

int n,K,ans;

int v[MAXN<<1],w[MAXN<<1],first[MAXN],next[MAXN<<1],en;

int dis[MAXN],En,last;

void AddEdge(const int &U,const int &V,const int &W)

{

	v[++en]=V;

	w[en]=W;

	next[en]=first[U];

	first[U]=en;

}

bool centroid[MAXN];

int size[MAXN];

int calc_sizes(int U,int Fa)

{

	int res=1;

	for(int i=first[U];i;i=next[i])

	  if(v[i]!=Fa&&(!centroid[v[i]]))

		res+=calc_sizes(v[i],U);

	return size[U]=res;

}

Point calc_centroid(int U,int Fa,int nn)

{

	Point res=make_pair(INF,-1);

	int sum=1,maxv=0;

	for(int i=first[U];i;i=next[i])

	  if(v[i]!=Fa&&(!centroid[v[i]]))

	    {

	      res=min(res,calc_centroid(v[i],U,nn));

	      maxv=max(maxv,size[v[i]]);

	      sum+=size[v[i]];

	    }

	maxv=max(maxv,nn-sum);

	res=min(res,make_pair(maxv,U));

	return res;

}

void calc_dis(int U,int Fa,int d)

{

	dis[En++]=d;

	for(int i=first[U];i;i=next[i])

	  if(v[i]!=Fa&&(!centroid[v[i]]))

	    calc_dis(v[i],U,d+w[i]);

}

int calc_pairs()

{

	sort(dis,dis+last);

	for(int i=last;i<En;++i)

	  ans+=(upper_bound(dis,dis+last,K-dis[i])-dis);

}

void solve(int U)

{

	calc_sizes(U,-1);

	int s=calc_centroid(U,-1,size[U]).second;

	centroid[s]=1;

	for(int i=first[s];i;i=next[i])

	  if(!centroid[v[i]])

	    solve(v[i]);

	En=0; dis[En++]=0;

	for(int i=first[s];i;i=next[i])

	  if(!centroid[v[i]])

	    {

	      last=En;

		  calc_dis(v[i],s,w[i]);

	      calc_pairs();

	    }

	centroid[s]=0;

}

int main()

{

	scanf("%d",&n);

	int a,b,c;

	for(int i=1;i<n;++i)

	  {

	  	scanf("%d%d%d",&a,&b,&c);

	  	AddEdge(a,b,c); AddEdge(b,a,c);

	  }

	scanf("%d",&K);

	solve(1);

	printf("%d\n",ans);

	return 0;

}