050：Tree

Messj

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

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output

8

Messj

理论参考https://wenku.baidu.com/view/8861df38376baf1ffc4fada8.html?re=view

树的分治

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<algorithm>
   
4. 
   
5. using namespace std;
   
6. const int maxn=10010;
   
7. int N,K;
   
8. int root;        //根结点
   
9. int ans;        //结果
   
10. int Max;       
    
11. struct node
    
12. {
    
13.         int v;
    
14.         int next;
    
15.         int w;
    
16. }edge[maxn*2];        //无向图
    
17. int tot;        //结点总数total
    
18. int head[maxn];        //头结点数组head
    
19. int size[maxn];        //以v为根的子树节点数size
    
20. int maxv[maxn];       
    
21. int vis[maxn];        //遍历标志visit
    
22. int dis[maxn];        //距离数组distance
    
23. int num;
    
24. void init()  
    
25. {  
    
26.     tot=0;  
    
27.     ans=0;  
    
28.     memset(head,-1,sizeof(head));  
    
29.     memset(vis,0,sizeof(vis));  
    
30. }   
    
31. //建立邻接表
    
32. void add_edge(int u,int v,int w)
    
33. {
    
34.         edge[tot].v=v;
    
35.         edge[tot].w=w;
    
36.         edge[tot].next=head[u];//形成了链表，以-1结尾，以head为头结点，每个结点都是结点u的孩子。
    
37.         head[u]=tot++;
    
38. }
    
39. //计算子树所含节点数
    
40. void dfssize(int u,int f) //除去f点外的规模，f一般为父结点
    
41. {
    
42.         size[u]=1;        //本身 一个结点
    
43.         maxv[u]=0;        //其最大子树的结点数
    
44.         for(int i=head[u];i!=-1;i=edge[i].next)
    
45.         {
    
46.                 int v=edge[i].v;
    
47.                 if(v==f||vis[v])
    
48.                         continue;
    
49.                 dfssize(v,u);
    
50.                 size[u]+=size[v];
    
51.                 if(size[v]>maxv[u])
    
52.                         maxv[u]=size[v];
    
53.         }
    
54. }
    
55. //确定树的重心，即最佳的根结点。
    
56. void dfsroot(int r,int u,int f)        //r为根结点，u为比较结点
    
57. {
    
58.         if(size[r]-size[u]>maxv[u])        //size[r]-size[u]是u上面部分的树的尺寸，maxv[u]是u的最大子树的结点数。
    
59.                 maxv[u]=size[r]-size[u];//此处将树看作二叉树，把最大子树作为一枝，剩余的看作一枝 。将最大的一枝存入maxv中
    
60.         if(maxv[u]<Max)        Max=maxv[u],root=u;  //MAX是maxv中最小值，由于maxv必不小于总结点的一半 ，故MAX存储的是当前最平衡结点的最大枝个数
    
61.         for(int i=head[u];i!=-1;i=edge[i].next)
    
62.         {
    
63.                 int v=edge[i].v;
    
64.                 if(v==f||vis[v])
    
65.                         continue;
    
66.                 dfsroot(r,v,u);
    
67.         }
    
68. }
    
69. //求每个点离重心的距离  
    
70. void dfsdis(int u,int d,int f)  
    
71. {
    
72.         dis[num++]=d;
    
73.         for(int i=head[u];i!=-1;i=edge[i].next)  
    
74.     {  
    
75.         int v=edge[i].v;  
    
76.         if(v!=f&&!vis[v])  
    
77.             dfsdis(v,d+edge[i].w,u);  
    
78.     }  
    
79. }
    
80. //计算以u为根的子树中有多少点对的距离小于等于K  
    
81. int calc(int u,int d)  //d为通向u的路径长度  
    
82. {  
    
83.     int ret=0;         //点对的个数
    
84.     num=0;  //初始化
    
85.     dfsdis(u,d,0);  
    
86.     sort(dis,dis+num);  
    
87.     int i=0,j=num-1;  //0点为根结点本身
    
88.     while(i<j)  
    
89.     {  
    
90.         while(dis[i]+dis[j]>K&&i<j)j--;  
    
91.         ret+=j-i;  
    
92.         i++;  
    
93.     }  
    
94.     return ret;  
    
95. }  
    
96. void dfs(int u)
    
97. {
    
98.         Max=N;
    
99.         dfssize(u,0);
    
100.         dfsroot(u,u,0);        //设置u为根
     
101.         ans+=calc(root,0);        //u树中的点对
     
102.         vis[root]=1;        //根结点已遍历
     
103.         for(int i=head[root];i!=-1;i=edge[i].next)  
     
104.     {  
     
105.         int v=edge[i].v;  
     
106.         if(!vis[v])  
     
107.         {  
     
108.             ans-=calc(v,edge[i].w);  //删除掉同属于v结点且满足 dis[i]+dis[j]<K的点对。
     
109.             dfs(v);  //加上以v为结点仅可过v结点满足 dis[i]+dis[j]<K的点对。
     
110.         }  
     
111.     }  
     
112. }
     
113. int main()
     
114. {
     
115.         while(scanf("%d%d",&N,&K)!=EOF)
     
116.         {
     
117.                 if(!N&&!K)
     
118.                         break;
     
119.                 int u,v,w;
     
120.                 init();
     
121.                 for(int i=1;i<N;i++)  
     
122.         {  
     
123.             scanf("%d%d%d",&u,&v,&w);  
     
124.             add_edge(u,v,w);  
     
125.             add_edge(v,u,w);  
     
126.         }
     
127.                 dfs(1);
     
128.                 printf("%d\n",ans);
     
129.         }
     
130.         return 0;
     
131. }

复制代码