首页 > 代码库 > POJ1741 Tree

POJ1741 Tree

2024-07-24 05:46:16   210人阅读

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

5
题解：
看了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\n",ans);134     }135 136      return 0;137 138 }
View Code

 

POJ1741 Tree


联系
我们