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

"把树上从x到y的路径上的边的数都+1" 这步如何快速实现呢?

Posted by RoBa at 2007-10-06 23:54:49 on Problem 3417
In Reply To:考虑树的基本环路系统……然后大概是这样…… Posted by:frkstyc at 2007-10-06 21:55:52

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

Followed by:

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

Post your reply here:

Home Page Go Back To top