poj 1741 Tree

点分治裸题23333这个题如果K很大的话就不能用依次处理每棵子树做了。（数组存不开2333）
这个就只能是总的依次减去每棵子树里的。
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<cmath>
 7 #define N 100005
 8 #define M 1000005
 9 #define LL long long
10 #define inf 0x3f3f3f3f
11 using namespace std;
12 inline int ra()
13 {
14     int x=0,f=1; char ch=getchar();
15     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
16     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
17     return x*f;
18 }
19 int n,K,cnt,sum,ans,root;
20 int head[10005],deep[10005],d[10005],f[10005],son[10005];
21 bool vis[10005];
22 struct data{int to,next,v;}e[20005];
23 void insert(int x, int y, int w)
24 {
25     e[++cnt].next=head[x]; e[cnt].to=y; e[cnt].v=w; head[x]=cnt;
26 }
27 void getroot(int x, int fa)
28 {
29     son[x]=1; f[x]=0;
30     for (int i=head[x];i;i=e[i].next)
31     {
32         if (e[i].to==fa || vis[e[i].to]) continue;
33         getroot(e[i].to,x);
34         son[x]+=son[e[i].to];
35         f[x]=max(f[x],son[e[i].to]);
36     }
37     f[x]=max(f[x],sum-son[x]);
38     if (f[x]<f[root]) root=x;
39 }
40 void getdeep(int x, int fa)
41 {
42     deep[++deep[0]]=d[x];
43     for (int i=head[x];i;i=e[i].next)
44     {
45         if (e[i].to==fa || vis[e[i].to]) continue;
46         d[e[i].to]=d[x]+e[i].v;
47         getdeep(e[i].to,x);
48     }
49 }
50 int cal(int x, int now)
51 {
52     d[x]=now; deep[0]=0;
53     getdeep(x,0);
54     sort(deep+1,deep+deep[0]+1);
55     int t=0,l,r;
56     for (l=1,r=deep[0];l<r;)
57     {
58         if (deep[l]+deep[r]<=K) t+=r-l,l++;
59         else r--;
60     }
61     return t;
62 }
63 void work(int x)
64 {
65     ans+=cal(x,0); vis[x]=1;
66     for (int i=head[x];i;i=e[i].next)
67     {
68         if (vis[e[i].to]) continue;
69         ans-=cal(e[i].to,e[i].v);
70         sum=son[e[i].to];
71         root=0;
72         getroot(e[i].to,root);
73         work(root);
74     }
75 }
76 int main()
77 {
78     while (1)
79     {
80         ans=0,root=0; cnt=0;
81         memset(vis,0,sizeof(vis));
82         memset(head,0,sizeof(head));
83         n=ra(); K=ra(); if (n==0) break;
84         for (int i=1; i<n; i++)
85         {
86             int x=ra(),y=ra(),w=ra();
87             insert(x,y,w); insert(y,x,w);
88         }
89         sum=n; f[0]=inf;
90         getroot(1,0);
91         work(root);
92         cout<<ans<<endl;
93     }
94     return 0;
95 }