朴素算法枚举两点为o(n^2) ,若用求树重心 采用分治策略可降至n(logn)^2;
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define INF 100010000 const int maxn = 10100; int n,d[maxn],K; struct node{ int to,val; node(int xx=0,int yy=0):to(xx),val(yy){} }; vector<node> son[maxn]; bool done[maxn]; int Focus,nown,MIN; void Get_Focus(int u,int fa){ d[u]=1; int max_ = 0; for(int i=0;i<son[u].size();i++) if(son[u][i].to!=fa&&!done[son[u][i].to]){ int v = son[u][i].to; Get_Focus(v,u); d[u]+=d[v]; max_=max(max_,d[v]); } max_=max(max_,nown-d[u]); if(MIN>max_){ MIN=max_; Focus=u; } } vector<int> V; int dis[maxn]; void get_distance(int u,int fa){ for(int i=0;i<son[u].size();i++) if(son[u][i].to!=fa&&!done[son[u][i].to]){ int v=son[u][i].to; dis[v]=dis[u]+son[u][i].val; V.push_back(dis[v]); get_distance(v,u); } } int cal(){ sort(V.begin(),V.end()); int ans=0; for(int i=0,j=V.size()-1;i<j;){ if(V[i]+V[j]<=K) ans+=j-i++; else j--; } return ans; } int res; void dfs(int root){ V.clear(); dis[root]=0; V.push_back(0); get_distance(root,-1); res+=cal(); done[root]=true; for(int i=0;i<son[root].size();i++)if(!done[son[root][i].to]) { V.clear(); int v=son[root][i].to; dis[v]=son[root][i].val; V.push_back(dis[v]); get_distance(v,root); res-=cal(); nown=V.size(); MIN=INF; Get_Focus(v,root); dfs(Focus); } } int main() { while(scanf("%d %d",&n,&K)==2){ if(!n&&!K) break; for(int i=1;i<=n;i++) son[i].clear(); int x,y,z; for(int i=0;i<n-1;i++){ scanf("%d %d %d",&x,&y,&z); son[x].push_back(node(y,z)); son[y].push_back(node(x,z)); } memset(done,false,sizeof(done)); nown=n; MIN=INF; Get_Focus(1,-1); res=0; dfs(Focus); printf("%d\n",res); } return 0; }