Tree
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 9112 | Accepted: 2726 |
Description
Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length
l.
The last test case is followed by two zeros.
l.
The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
5 4 1 2 3 1 3 1 1 4 2 3 5 1 0 0
Sample Output
8
Source
题意:求满足dis(i,j)<=k,即距离小于等于k的点对的数目
题解:对树的点进行分治,用O(n)的算法处理出对于某个点到其他节点的距离,然后O(nlogn)排序,显然再用O(n)的算法就可以算出某2个距离和小于等于k的结点对数(包含在同一棵子树的2个结点对),然后就分别用O(n)遍历子树,减去所有在同一棵子树的结点对数,这样就完成了一次分治。对于树所要删除进行分治的点,最好选择该树(子树)的重心。。。。本人表达捉急。。。详细见代码。。。附带,总时间复杂度为O(nlogn)
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 10008 struct edge{ int to,len,next; }p[MAXN*2]; int head[MAXN],son[MAXN],mark[MAXN]; int d[MAXN],dis[MAXN],cou; int all,root,rsize,n,m,ans; int MAX(int x,int y){ return x>y?x:y; } int MIN(int x,int y){ return x<y?x:y; } int cmp(const void *a,const void *b) { return *(int *)a<*(int *)b?-1:1; } void add(int x,int y,int len) { p[all].to=y; p[all].len=len; p[all].next=head[x]; head[x]=all++; } void getroot(int x,int f) { int res=0,i; son[x]=0; for(i=head[x];i!=-1;i=p[i].next) { if(mark[p[i].to]||p[i].to==f) continue; getroot(p[i].to,x); son[x]+=son[p[i].to]; res=MAX(res,son[p[i].to]); } son[x]++; res=MAX(res,n-son[x]); if(rsize>res) rsize=res,root=x; } void getdis(int x,int f) { int i; d[cou++]=dis[x]; for(i=head[x];i!=-1;i=p[i].next) { if(mark[p[i].to]||p[i].to==f) continue; dis[p[i].to]=dis[x]+p[i].len; getdis(p[i].to,x); } } int mycount(int x,int len) { int res=0,l,r; dis[x]=len; cou=0; getdis(x,-1); qsort(d,cou,sizeof(d[0]),cmp); for(l=0,r=cou-1;l<r;) { if(d[l]+d[r]<=m) res+=r-l++; else r--; } return res; } void solve(int x) { int i; ans+=mycount(x,0); mark[x]=1; for(i=head[x];i!=-1;i=p[i].next) { if(mark[p[i].to]) continue; ans-=mycount(p[i].to,p[i].len); root=rsize=n=son[x]; getroot(p[i].to,-1); solve(root); } } int main() { int x,y,z,i; while(scanf("%d%d",&n,&m),n+m) { memset(head,-1,sizeof(head)); memset(mark,0,sizeof(mark)); for(all=i=0;i<n-1;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } root=rsize=n,ans=0; getroot(1,-1); solve(root); printf("%d\n",ans); } return 0; }