「POJ1741」Tree

2014年6月15日9,53812

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

题解

复习了一下点分治,准确的说上次学的时候根本没有学会T T

发现确实比链分治简单不少

所谓点分治 对于一条树路径 只有经过或不经过一个点的情况

对于不经过的情况 把一棵树按这个点拆成好几棵分治就行了

考虑经过这个点的情况

对于这题 可以对这个点延伸出的几棵子树各做一次dfs

记录子树中出现的距离值

对于一棵树的距离值数组

把它排序求一次ans1

再对每棵子树分别求一个自己对自己的ans2

\(ans1-\sum ans2\)即为最后的ans

也可以用平衡树来维护信息

考虑经过根的路径,依次处理其子树,维护平衡树,对于第S棵子树其每个结点x,在平衡树中查询出发点为根,终点在S-1子树中,小于K-dis[x]+1的路径数量num,ans+=num

再用S更新平衡树

1.点分治+排序

2.点分治+treap

 

avatar
4 Comment threads
8 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
hzwery20070316wulala蒻cjk_steps Recent comment authors
  Subscribe  
提醒
YXR童鞋

黄学长QAQ 感觉您的重心找的不对啊 求轻喷

y20070316
y20070316

扑通扑通跪下来,千古神犇黄哲威

De℃,.: )
De℃,.: )

学长博客前几天都打不开QAQ

cjk_steps
cjk_steps

请问每次getroot()以后,需不需要把原来树中root的父结点的son值更新为sum-size[root]?因为getroot()以后原树中root的父结点会变为root的子结点。