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 wangfangbob at 2007-10-07 20:10:31 on Problem 3417 and last updated at 2007-10-07 20:15:41
In Reply To:啥lca-rmq, 根本就是后序遍历+树型dp,O(n)复杂度,怪不得我的线段树超时! Posted by:wangfangbob at 2007-10-07 12:46:42

dfs给树标号,使得所有的子树标号是连续区间,对于每个节点到其父亲的边,要判断从这个节点的
子树连到树外的新边数量,从而转化成有多少新边是从区间内部指向区间外部.对于一条新边(a,b), 
开个数组把a点赋成b,b点赋成a,然后就变成统计区间内的值有没有小于区间左端点,或者大于
区间有端点,是否唯一等等...然后用线段树(不过会tle^_^),或者直接从叶子到根递推就可
以了.基本思想就是这样,具体处理新边的时候并不是简单的赋值,要处理一些细节.

Followed by:

确实。。不错的方法！ (2) ogogo 2007-10-07 20:30:49
Re:我的歪招! (19) uncia 2012-08-04 10:49:42

Post your reply here:

Home Page Go Back To top