POJ1741 Tree

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N（n<=40000）接下来n-1行边描述管道，按照题目中写的输入接下来是k

Output

一行，有多少对点之间的距离小于等于k

Sample Input

7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10

Sample Output

题解：
看了hzwer的代码感觉豁然开朗，这题的点分居然这么简单，原来一直以为相当难。。。
基本思路就是
找重心+统计+去重+点分治
算法的实现有很多细节，hzwer的代码十分优美。学习了。
代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 40000+1000
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 struct edge{int go,next,w;}e[2*maxn];
 61 int ans,tot,sum,n,k,root,head[maxn],s[maxn],f[maxn],deep[maxn],d[maxn];
 62 bool vis[maxn];
 63 inline void insert(int x,int y,int z)
 64 {
 65     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z;
 66     e[++tot].go=x;e[tot].next=head[y];head[y]=tot;e[tot].w=z;
 67 }
 68 inline void getroot(int x,int fa)
 69 {
 70     s[x]=1;f[x]=0;
 71     for(int i=head[x],y;i;i=e[i].next)
 72     {
 73         if(vis[y=e[i].go]||y==fa)continue;
 74         getroot(y,x);
 75         s[x]+=s[y];
 76         f[x]=max(f[x],s[y]);
 77     }
 78     f[x]=max(f[x],sum-s[x]);
 79     if(f[x]<f[root])root=x;
 80 }
 81 inline void getdeep(int x,int fa)
 82 {
 83     deep[++deep[0]]=d[x];
 84     for(int i=head[x],y;i;i=e[i].next)
 85     {
 86         if(vis[y=e[i].go]||y==fa)continue;
 87         d[y]=d[x]+e[i].w;
 88         getdeep(y,x);
 89     }
 90 }
 91 inline int calc(int x,int now)
 92 {
 93     deep[0]=0;d[x]=now;
 94     getdeep(x,0);
 95     sort(deep+1,deep+deep[0]+1);
 96     int t=0;
 97     for(int l=1,r=deep[0];l<r;)
 98     if(deep[l]+deep[r]<=k){t+=r-l;l++;}else r--;
 99     return t;
100 }
101 inline void work(int x)
102 {
103     vis[x]=1;
104     ans+=calc(x,0);
105     for(int i=head[x],y;i;i=e[i].next)
106     {
107         if(vis[y=e[i].go])continue;
108         ans-=calc(y,e[i].w);
109         sum=s[y];
110         root=0;
111         getroot(y,0);
112         work(root);
113     }
114 }
115 
116 int main()
117 
118 {
119 
120     freopen("input.txt","r",stdin);
121 
122     freopen("output.txt","w",stdout);
123     while(1)
124     {
125      memset(head,0,sizeof(head));tot=ans=0;
126      memset(vis,0,sizeof(vis));
127 
128      n=read();k=read();if(n==0)break;
129      for1(i,n-1){int x=read(),y=read(),z=read();insert(x,y,z);};
130      sum=n;f[root=0]=inf;
131      getroot(1,0);
132       work(root);
133      printf("%d
",ans);
134     }
135 
136      return 0;
137 
138 }

View Code