POJ1741 Tree

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.

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.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

Source

LouTiancheng@POJ

树的重心：树上有一个结点,其所有的子树中最大的子树节点数最少,这个点就是这棵树的重心

点分治：先找出树的重心作为树根，统计其子树的答案，然后递归处理各子树，并去除重复算的答案。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<cstring>
  6 using namespace std;
  7 const int mxn=30200;
  8 //base
  9 int n,k;
 10 int ans;
 11 //node
 12 struct edge{
 13     int nx,to;
 14     int w;
 15 }e[40020];
 16 int head[mxn],size[mxn],mc[mxn],dis[mxn];//邻接表队首  点的子树尺寸 点重量 结点深度
 17 int cnt;
 18 //tree
 19 int root,mn=mxn;
 20 int tot;
 21 bool vis[mxn];
 22 // 
 23 void add_edge(int u,int v,int len){
 24     e[++cnt]=(edge){head[u],v,len};head[u]=cnt;
 25     e[++cnt]=(edge){head[v],u,len};head[v]=cnt;
 26 }
 27 void dfssize(int u,int fa){//求结点子树尺寸 
 28     size[u]=1;
 29     mc[u]=0;
 30     for(int i=head[u];i;i=e[i].nx){
 31         int v=e[i].to;
 32         if(v!=fa && !vis[v]){
 33             dfssize(v,u);
 34             size[u]+=size[v];
 35             mc[u]=size[v]>mc[u]? size[v]:mc[u];
 36         }
 37     }
 38     return;
 39 }
 40 void findmc(int u,int fa,int rt){//求树的重心 
 41     mc[u]=max(mc[u],size[rt]-size[u]);
 42     if(mc[u]<mn){mn=mc[u];root=u;}//符合要求则更新树根 
 43     for(int i=head[u];i;i=e[i].nx){
 44         int v=e[i].to;
 45         if(v!=fa && !vis[v])findmc(v,u,rt);
 46     }
 47     return;
 48 }
 49 void dist(int u,int fa,int d){//求u的子树的结点深度 
 50     dis[++tot]=d;
 51     for(int i=head[u];i;i=e[i].nx){
 52         int v=e[i].to;
 53         if(v!=fa && !vis[v])
 54             dist(v,u,d+e[i].w);
 55     }
 56 }
 57 int calc(int x,int d){//计算以x为中心，所有经过x的路径上符合要求的点对的数量 
 58     int res=0;
 59     tot=0;
 60     dist(x,0,d);//计算x为根的树的各结点深度 
 61     sort(dis+1,dis+tot+1);//深度由小到大排序 
 62     int l=1,r=tot;
 63     while(l<r){
 64         while(dis[l]+dis[r]>k && l<r )r--;//两结点深度相加就是距离 
 65         res+=r-l;
 66         l++;
 67     }
 68     return res;
 69 }
 70 
 71 void dfs(int rt){//处理以rt为根的子树 
 72 //    printf("test!: %d  %d
",rt,root);
 73     mn=n;//记得 
 74     dfssize(rt,0);
 75     findmc(rt,0,rt);
 76     ans+=calc(root,0);//在以rt为根的子树中找到重心后，以其为中心计算符合要求的点对数 
 77     vis[root]=1;
 78     for(int i=head[root];i;i=e[i].nx){
 79         int v=e[i].to;
 80         if(!vis[v]){
 81             ans-=calc(v,e[i].w);//减去以v为中心的答案数，避免之后计算重复 
 82             dfs(v);
 83         }
 84     }    
 85 }
 86 int main(){
 87     while(scanf("%d",&n) && n){
 88         memset(vis,0,sizeof(vis));
 89         memset(head,0,sizeof(head));
 90         ans=0;
 91         cnt=0;//初始化！初始化！
 92         scanf("%d",&k);
 93         for(int i=1,u,v,d;i<n;i++){
 94             scanf("%d%d%d",&u,&v,&d);
 95             add_edge(u,v,d);
 96         }
 97         dfs(1);//随便找个结点开始计算 
 98         printf("%d
",ans);
 99     }
100     return 0;
101 }