Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 15548		Accepted: 5054

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.

Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.

Write a program that will count how many pairs which are valid for a given tree.

The
input contains several test cases. The first line of each test case
contains two integers n, k. (n<=10000) The following n-1 lines each
contains three integers u,v,l, which means there is an edge between node
u and v of length l.

The last test case is followed by two zeros.

For each test case output the answer on a single line.

5 4

1 2 3

1 3 1

1 4 2

3 5 1

0 0

8

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N =  +;

 const int INF = 1e9;

 struct Edge{

     int u,v,w;

     Edge(int u=,int v=,int w=):u(u),v(v),w(w){};

 };

 int n,K,l1,l2,tl,ans;

 int siz[N],d[N],list[N],f[N],can[N];

 vector<Edge> es;

 vector<int> g[N];

 void adde(int u,int v,int w) {

     es.push_back(Edge(u,v,w));

     int m=es.size(); g[u].push_back(m-);

 }

 void init() {

     ans=; es.clear();

     memset(can,,sizeof(can));

     for(int i=;i<=n;i++) g[i].clear();

 }

 void dfs1(int u,int fa) {

     siz[u]=;

     list[++tl]=u;

     for(int i=;i<g[u].size();i++) {

         int v=es[g[u][i]].v;

         if(v!=fa && can[v]) {

             dfs1(v,u);

             f[v]=u; siz[u]+=siz[v];

         }

     }

 }

 int getroot(int u,int fa) {                    //寻找u子树重心

     int pos,mn=INF;

     tl=;

     dfs1(u,fa);

     for(int i=;i<=tl;i++) {

         int y=list[i],d=;

         for(int j=;j<g[y].size();j++) {

             int v=es[g[y][j]].v;

             if(v!=f[y] && can[v]) d=max(d,siz[v]);

         }

         if(y!=u) d=max(d,siz[u]-siz[y]);      //上方

         if(d<mn) mn=d , pos=y;                //使大子结点数最小

     }

     return pos;

 }

 void dfs2(int u,int fa,int dis) {

     list[++l1]=u; d[u]=dis;

     for(int i=;i<g[u].size();i++) {

         int v=es[g[u][i]].v;

         if(v!=fa && can[v]) dfs2(v,u,dis+es[g[u][i]].w);

     }

 }

 int getans(int* a,int l,int r) {

     int res=,j=r;

     for(int i=l;i<=r;i++) {

         while(d[a[i]]+d[a[j]]>K && j>i) j--;

         res+=j-i; if(i==j) break;

     }

     return res;

 }

 bool cmp(const int& x,const int& y) { return d[x]<d[y]; }

 void solve(int u,int fa) {

     int root=getroot(u,fa);

     l1=l2=;

     for(int i=;i<g[root].size();i++) {        //统计 d[i]+d[j]<=K && belong[i]==belong[j]

         int v=es[g[root][i]].v;

         if(can[v]) {

             l2=l1;

             dfs2(v,root,es[g[root][i]].w);    //insert[以v为根的子树]

             sort(list+l2+,list+l1+,cmp);

             ans-=getans(list,l2+,l1);

         }

     }

     list[++l1]=root; d[root]=can[root]=;

     sort(list+,list+l1+,cmp);

     ans+=getans(list,,l1);                    //统计d[i]+d[j]<=K

     for(int i=;i<g[root].size();i++) {        //递归<-分治

         int v=es[g[root][i]].v;

         if(v!=fa && can[v]) solve(v,root);

     }

 }

 int main() {

     while(scanf("%d%d",&n,&K)== && (n&&K)) {

         int u,v,w;

         init();

         for(int i=;i<n-;i++) {

             scanf("%d%d%d",&u,&v,&w);

             adde(u,v,w) , adde(v,u,w);

         }

         solve(,-);

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

     }

     return ;

 }