- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<vector>
- #define GroupSize 10025
- using namespace std;
- vector<int> G[GroupSize],E[GroupSize];
- int Depth[GroupSize],Belong[GroupSize],hash[GroupSize],sum[GroupSize],maxv[GroupSize];
- bool vis[GroupSize];
- int N,K,Sts,T,Ans;
- int cmp0(const void * x,const void * y)
- {
- int Px=*(int *)x,Py=*(int *)y;
- if (Depth[Px]<Depth[Py]) return -1;
- else if (Depth[Px]==Depth[Py]) return 0;
- else return 1;
- }
- int cmp1(const void * x,const void * y)
- {
- int Px=*(int *)x,Py=*(int *)y;
- if (Belong[Px]<Belong[Py]) return -1;
- else if (Belong[Px]>Belong[Py]) return 1;
- else if (Depth[Px]<Depth[Py]) return -1;
- else if (Depth[Px]==Depth[Py]) return 0;
- else return 1;
- }
- void dfs(int Root,int father)
- {
- hash[++Sts]=Root;
- sum[Root]=1;
- maxv[Root]=0;
- for (int i=0;i<G[Root].size();i++)
- {
- int v=G[Root][i];
- if (v==father || vis[v]) continue;
- dfs(v,Root);
- sum[Root]+=sum[v];
- maxv[Root]=maxv[Root]>sum[v] ? maxv[Root]:sum[v];
- }
- }
- int GetRoot(int Root,int father)
- {
- Sts=0;
- dfs(Root,father);
- int Cnt=sum[Root],Min=0x7FFFFFFF,Tr;
- for (int i=1;i<=Sts;i++)
- {
- int v=hash[i];
- int tmp=maxv[v]>Cnt-sum[v] ? maxv[v]:Cnt-sum[v];
- if (tmp<Min)
- {
- Min=tmp;
- Tr=v;
- }
- }
- return Tr;
- }
- void find(int Root,int father)
- {
- for (int i=0;i<G[Root].size();i++)
- {
- int v=G[Root][i];
- if (v==father || vis[v]) continue;
- if (Depth[Root]+E[Root][i]<=K)
- {
- hash[++T]=v;
- Depth[v]=Depth[Root]+E[Root][i];
- Belong[v]=Belong[Root];
- find(v,Root);
- }
- }
- }
- void GetNear(int Root,int father)
- {
- T=0;
- hash[0]=Root;
- Depth[Root]=0;
- Belong[Root]=father;
- for (int i=0;i<G[Root].size();i++)
- {
- int v=G[Root][i];
- if (v==father || E[Root][i]>K || vis[v]) continue;
- hash[++T]=v;
- Depth[v]=E[Root][i];
- Belong[v]=v;
- find(v,Root);
- }
- }
- int CountAll()
- {
- int R=T,ans=0;
- for (int i=1;i<=T;i++)
- {
- while (Depth[hash[i]]+Depth[hash[R]]>K && R>=1) R--;
- ans+=R;
- if (R>=i) ans--;
- }
- ans/=2;
- for (int i=1;i<=T;i++)
- if (Depth[hash[i]]<=K) ans++;
- return ans;
- }
- int CountRepeat()
- {
- int L=1,R,Cur,ans=0;
- while (L<=T)
- {
- for (int i=L;i<=T;i++)
- if (i==T || Belong[hash[i]]!=Belong[hash[i+1]])
- {
- Cur=R=i;
- break;
- }
- for (int i=L;i<=R;i++)
- {
- while (Depth[hash[i]]+Depth[hash[Cur]]>K && Cur>=L) Cur--;
- ans+=Cur-L+1;
- if (Cur>=i) ans--;
- }
- L=R+1;
- }
- return ans/2;
- }
- void solve(int Root,int father)
- {
- Root=GetRoot(Root,father);
- vis[Root]=true;
- GetNear(Root,father);
- qsort(&hash[1],T,sizeof(int),cmp0);
- Ans+=CountAll();
- qsort(&hash[1],T,sizeof(int),cmp1);
- Ans-=CountRepeat();
- for (int i=0;i<G[Root].size();i++)
- {
- int v=G[Root][i];
- if (v==father || vis[v]) continue;
- solve(v,Root);
- }
- }
- int main()
- {
- while (scanf("%d%d",&N,&K)!=EOF)
- {
- if (N+K==0) return 0;
- for (int i=1;i<=N;i++) G[i].clear();
- for (int i=1;i<=N;i++) E[i].clear();
- for (int i=1;i<N;i++)
- {
- int x,y,c;
- scanf("%d%d%d",&x,&y,&c);
- G[x].push_back(y);
- G[y].push_back(x);
- E[x].push_back(c);
- E[y].push_back(c);
- }
- memset(vis,0,sizeof(vis));
- Ans=0;
- solve(1,-1);
- printf("%d\\n",Ans);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/251120137474.html
来源: http://www.codesnippet.cn/detail/251120137474.html