【POJ 1741】 Tree (树的点分治)

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<cmath>
  8 using namespace std;
  9 #define Maxn 10010
 10 #define INF 0xfffffff
 11 
 12 struct node
 13 {
 14     int x,y,c,next;
 15 }t[Maxn*2];int len;
 16 int first[Maxn];
 17 int n,k;
 18 
 19 int mymax(int x,int y) {return x>y?x:y;}
 20 
 21 void ins(int x,int y,int c)
 22 {
 23     t[++len].x=x;t[len].y=y;t[len].c=c;
 24     t[len].next=first[x];first[x]=len;
 25 }
 26 int rt;
 27 bool q[Maxn];
 28 int sm[Maxn],mx[Maxn],dep[Maxn];
 29 int v[Maxn],vl;
 30 
 31 void dfs(int x,int h,int f)
 32 {
 33     mx[x]=-1;sm[x]=1;
 34     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])
 35     {
 36         int y=t[i].y;//dep[y]=dep[x]+t[i].c;
 37         dfs(y,h,x);
 38         sm[x]+=sm[y];
 39         mx[x]=mymax(mx[x],sm[y]);
 40     }
 41     mx[x]=mymax(mx[x],h-sm[x]);
 42     if(mx[x]<mx[rt]) rt=x;
 43 }
 44 
 45 int get_ans()
 46 {
 47     int now=1,ans=0;
 48     sort(v+1,v+1+vl);
 49     for(int i=vl;i>=1;i--)
 50     {
 51         if(now>i) now=i;
 52         while(v[i]+v[now]<=k&&now<i) now++;
 53         ans+=now-1;
 54     }
 55     return ans;
 56 }
 57 
 58 void dfs2(int x,int f)
 59 {
 60     v[++vl]=dep[x];
 61     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])
 62     {
 63         int y=t[i].y;
 64         dep[y]=dep[x]+t[i].c;
 65         dfs2(y,x);
 66     }
 67 }
 68 
 69 int fans;
 70 
 71 void ffind(int x,int f)
 72 {
 73     vl=0;dep[x]=0;dfs2(x,0);
 74     fans+=get_ans();
 75     q[x]=0;
 76     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])
 77     {
 78         int y=t[i].y;
 79         vl=0;dfs2(y,x);
 80         fans-=get_ans();
 81     }int i;
 82     for(i=first[x];i;i=t[i].next) 
 83         if(t[i].y!=f&&q[t[i].y])
 84     {
 85         rt=0;
 86         dfs(t[i].y,x,sm[t[i].y]);
 87         ffind(rt,x);
 88     }
 89 }
 90 
 91 int main()
 92 {
 93     while(1)
 94     {
 95         scanf("%d%d",&n,&k);
 96         if(n==0&&k==0) break;
 97         memset(first,0,sizeof(first));
 98         len=0;
 99         for(int i=1;i<n;i++)
100         {
101             int x,y,c;
102             scanf("%d%d%d",&x,&y,&c);
103             ins(x,y,c);ins(y,x,c);
104         }
105         fans=0;
106         memset(q,1,sizeof(q));
107         mx[0]=INF;
108         rt=0;vl=0;dfs(1,n,0);
109         ffind(rt,0);
110         printf("%d\n",fans);
111     }
112     return 0;
113 }