【poj1741】Tree

2014年6月15日5,70812

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

 

  • cjk_steps2015年2月13日 下午9:54 回复

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

    #1  
    • hzwer2015年2月13日 下午10:10 回复
      admin

      一般情况也影响不了运行时间,我测过 TAT

      #11
      • cjk_steps2015年2月13日 下午10:11 回复

        orz折腾了好久。。。

        #12
        • cjk_steps2015年2月13日 下午10:15 回复

          神犇WC考得怎么样?

          #13
          • hzwer2015年2月13日 下午10:26
            admin

            RAR 和没分似的

            #14
      • 2015年2月16日 上午9:42 回复

        这个可以证明的吗。。还是可以构造卡掉?我一直没想通怎么可以卡掉orz求教育

        #12
        • hzwer2015年2月16日 下午12:31 回复
          admin

          哦可以证明吧,即使能卡掉,同一棵树不同的写法也可能找出不同重心

          #13
        • wulala2015年2月22日 下午7:35 回复

          卡不掉

          #13
  • De℃,.: )2015年2月22日 下午10:48 回复

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

    #2  
  • y200703162015年8月22日 下午12:53 回复

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

    #3  
  • YXR童鞋2016年1月24日 下午10:40 回复

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

    #4  
    • hzwer2016年1月25日 下午8:10 回复
      admin

      分治的时候不太对,但是我觉得实际上也没什么关系
      楼下有人问了

      #41