poj1741 树上的分治

题意是说给了n个点的树n<=10000,问有多少个点对例如(a,b)他们的之间的距离小于等于k 采用树的分治做

#include <iostream>

#include <cstdio>

#include <string.h>

#include <algorithm>

#include <vector>

using namespace std;

const int maxn=;

int H[maxn],nx[maxn*],to[maxn*],numofE,dist[maxn*];

void add(int u, int v, int d)

{

    numofE++;

    dist[numofE]=d,

    to[numofE]=v,

    nx[numofE]=H[u],

    H[u]=numofE;

}

void init(int N)

{

   numofE=;

   memset(H,,sizeof(H));

}

int ans;

bool center[maxn];

int subnum[maxn];

int Q[maxn+],fa[maxn];

int searchroot(int cur)

{

     int rear=,root=cur;

     Q[rear++]=cur;fa[cur]=;

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

         int x= Q[i];

         for(int j=H[x]; j; j=nx[j])

            if(to[j]!=fa[x]&& center[ to[j] ]==false)

              Q[rear++]=to[j],fa[to[j]]=x;

     }

     int MIN=;

     for(int i=rear-; i>=; i--){

         int x=Q[i];

subnum[x]=;

int MA=;

         for(int j=H[x]; j ; j=nx[j])

            if(to[j]!=fa[x]&&center[ to[j] ]==false)

                MA=max(MA,subnum[to[j]]),subnum[x]+=subnum[to[j]];

         MA=max(MA,rear-subnum[ x ]);

         if(MIN>MA)MIN=MA,root=x;

     }

     return root;

}

int P[maxn];

int N,K;

int count_pair(int s, int t){

   int ge=,R=t;

   for(int i=s; i<t; i++)

    {

        while(R>s&&P[R-]+P[i]>K)R--;

        ge+=R-s-(R>i?:);

    }

   return ge/;

}

void updateedg(int s, int cur, int d)

{

     int rear=;

     Q[rear++]=cur; fa[cur]=;P[s]=d;

     for(int i=; i<rear; i++)

     {

         int x=Q[i];

         for(int j=H[x]; j; j=nx[j])

         {

             int tto=to[j];

             if(center[tto]||tto==fa[x])continue;

             P[s+rear]=P[s+i]+dist[j],Q[rear++]=tto,fa[tto]=x;

         }

     }

     sort(P+s,P+s+rear);

}

int dfs(int s,int cur,int d)

{

    int root,tot=;

    root=searchroot(cur);

    center[root]=true;

    for(int i=H[root]; i ; i=nx[i])

    {

         int tto=to[i];

         if(center[tto])continue;

         int n=dfs(s+tot,tto,dist[i]);

         ans-=count_pair(s+tot,s+tot+n);

         tot+=n;

    }

    P[s]=;

    sort(P+s,P+s+tot);

    ans+=count_pair(s,s+tot);

    center[root]=false;

    updateedg(s,cur,d);

    return tot;

}

int main()

{

    memset(center,false,sizeof(center));

    while(scanf("%d%d",&N,&K)==)

        {

             if(!N&&!K)break;

              ans=;

              init(N);

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

                int a,b,d;

                scanf("%d%d%d",&a,&b,&d);

                add(a,b,d);add(b,a,d);

              }

              dfs(,,);

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

        }

    return ;

}