題目鏈接：http://www.lydsy.com/JudgeOnline/PRoblem.php?id=3365

題解：點分治的題

（對于點分治初學者，簡單概括一下點分治）：點分治通過遞歸的方式不斷找到子樹的重心，然后以當前的子樹的重心為根，統(tǒng)計該子樹內所有點到根（重心）的距離并存放到一個數組里，然后在距離數組里做一些事情。點分治的時間復雜度為nlogn*(對距離數組做的事情的時間復雜度)

樹的重心：找到一個點，使其作為樹根，其最大子樹的節(jié)點個數最少

說這道題：點分治裸題，把距離數組排序后用雙指針l,rO(n)掃描，對于每一個l，有多少個l<i<=r使得len[i]+len[l]<=k,最后輸出答案(因為點分治這種做法會有在同一顆子樹的兩個距離被計算入答案的情況，所以要把其所有子樹的答案刪除

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;const int inf=1e9+7;const int N=80005;const int M=160005;int maxn,siz[N],s[N],dis[N];int n,m,K,cnt,G,sum,ans,h,lj[N],nxt[M],w[M],to[M];bool vis[N];void ins(int f,int t,int p) {cnt++,to[cnt]=t,nxt[cnt]=lj[f],lj[f]=cnt,w[cnt]=p;}void add(int f,int t,int p) {ins(f,t,p),ins(t,f,p);}void findG(int x,int fa){    siz[x]=1;	int mx=0;    for(int i=lj[x];i;i=nxt[i])    if(to[i]!=fa&&!vis[to[i]])    {        findG(to[i],x);        siz[x]+=siz[to[i]];        mx=max(mx,siz[to[i]]);    }    mx=max(mx,sum-siz[x]);    if(mx<maxn) maxn=mx,G=x;}void dfs(int x,int fa){    s[++h]=dis[x];    for(int i=lj[x];i;i=nxt[i])    if(to[i]!=fa&&!vis[to[i]])    {        dis[to[i]]=dis[x]+w[i];        dfs(to[i],x);    }}int cal(int x,int now){	dis[x]=now;	h=0;    dfs(x,0);    sort(s+1,s+h+1);    int ans=0,l=1,r=h;    while(l<r)    {		if(s[l]+s[r]<=K) ans+=r-l,l++;		else r--;    }    return ans;}void solve(int x){    ans+=cal(x,0);    vis[x]=1;    for(int i=lj[x];i;i=nxt[i])    if(!vis[to[i]])    {        ans-=cal(to[i],w[i]);        G=0;        maxn=inf;		sum=siz[to[i]];        findG(to[i],0);        solve(G);    }}int main(){	scanf("%d%d",&n,&m);	int u,v,w;    char ss[5];	for(int i=1;i<=m;i++)    {    	scanf("%d%d%d%s",&u,&v,&w,&ss);    	add(u,v,w);    }    scanf("%d",&K);    G=0;	sum=n,maxn=inf;    findG(1,0);    solve(G);    printf("%d/n",ans);}