Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

考虑树的基本环路系统……然后大概是这样……

Posted by frkstyc at 2007-10-06 21:55:52 on Problem 3417 and last updated at 2007-10-06 22:02:48
In Reply To:弱问一下这题怎么做...看了解题报告一头雾水... Posted by:RoBa at 2007-10-06 21:19:48

给树的每条边标一个数，开始都是0。每一条额外的边把两个顶点x和y接起来，就把树上从x到y的路径上的边
的数都+1。这样搞完之后，算一下有多少条树边的数是0，把这个数目记成S。然后再枚举每一条额外的边，
数一下两个端点x和y之间在树里的路径中有多少条边的数是1，把这个数目累加到T。S*M+T....
关键是折腾数据结构……

Followed by:

"把树上从x到y的路径上的边的数都+1" 这步如何快速实现呢? (174) RoBa 2007-10-06 23:54:49
- up (0) RoBa 2007-10-07 12:16:31
  - Re:up (102) cuiaoxiang 2007-10-07 12:45:32
    - 赞，明白了 (112) RoBa 2007-10-07 21:48:42
      - 同赞~~ (0) frkstyc 2007-10-07 21:55:46
    - Re:up (6) boys 2007-10-08 10:40:40
    - Good Thought! (112) cfdream 2007-10-10 17:08:31
其实还有种简单些的方法…… (85) hhb 2009-05-05 21:43:11

Post your reply here:

Home Page Go Back To top