5 41 2 31 3 11 4 23 5 10 0Sample Output
8（說起來這應(yīng)該是人生第一道點分治唄。。。quq蒟蒻的悲哀：）題意：給定一棵N(1<= N <=10000)個結(jié)點的帶權(quán)樹，定義dist(u,v)為u,v兩點間的最短路徑長度，路徑的長度定義為路徑上所有邊的權(quán)和。再給定一個 K  ，如果對于不同的兩個結(jié)點a,b，如果滿足dist(a,b) <=K，則稱(a,b)為合法點對。求合法點對個數(shù)。題解：也是剛剛搞完點分治唄。。。%XZK難得一次編譯過AC。。。所謂點分治嘞，就是在一個無根樹里選取一個點作為根【重心】然后再遞歸處理每個子樹對于這道題嘛，我們考慮一條路徑只有兩種情況——經(jīng)過根or不過根【也可以說是：兩點在同一棵子樹內(nèi)or不在同一顆子樹內(nèi)】那么我們就可以得出一個大致框架：記錄每個子樹內(nèi)的到子樹【我們遞歸處理的樹】根節(jié)點距離值，然后從小到大排一個序，就可以計算出符合dist(a,b)<=k的點對個數(shù)，用這種方法對每一個子樹計一個res表示合法點對數(shù)這個時候要注意：對于一棵這樣的樹 ，由于遞歸的緣故，會有重復(fù)計算的情況所以我們的結(jié)果ans=ans-sigama res的【即：所有滿足合法的點對-在同一個子樹的點對數(shù)】以下是AC代碼：=v=
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define inf 0x7fffffff#define maxn 10010using namespace std;struct node{	int v,w,nxt;}e[maxn*4];int n,k;int vis[maxn];int dis[maxn],dep[maxn];int size[maxn],f[maxn];int head[maxn],cnt;int rt,cd;void add(int u,int v,int w){	e[++cnt].v=v;	e[cnt].w=w;	e[cnt].nxt=head[u];	head[u]=cnt;}void getroot(int x,int fa,int sum){	size[x]=1;f[x]=0;	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v] && v!=fa){			getroot(v,x,sum);			size[x]+=size[v];			f[x]=max(f[x],size[v]);		}	}	f[x]=max(f[x],sum-size[x]);	if(f[x]<f[rt])rt=x;	}void getdeep(int x,int fa){	dis[++cd]=dep[x];	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v] && v!=fa){			dep[v]=dep[x]+e[i].w;			getdeep(v,x);		}	}}int work(int x,int val){	dep[x]=val;cd=0;	getdeep(x,0);	sort(dis+1,dis+cd+1);	int res=0,l=1,r=cd;	while(l<r){		if(dis[l]+dis[r]<=k)res+=r-l,l++;		else r--;	}	return res;}int ans;void solve(int x){	ans+=work(x,0);	vis[x]=1;	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v]){			ans-=work(v,e[i].w);			rt=0;			getroot(v,rt,size[v]);			solve(rt);		}	}}int main(){	while(~scanf("%d%d",&n,&k)){		if(n==0 && k==0)break;		ans=0,rt=0;		memset(head,-1,sizeof head);memset(vis,0,sizeof vis);		cnt=0;		memset(size,0,sizeof size);		for(int i=1;i<n;i++){			int u,v,w;scanf("%d%d%d",&u,&v,&w);			add(u,v,w);add(v,u,w);		}		f[0]=inf;		getroot(1,0,n);		solve(rt);		printf("%d/n",ans);	}	return 0;}8