正规、严谨、精妙。 -POI
发现POI(波兰信息学奥赛)的题都很有意思。于是开刷bzoj上的poi题目(按ac人数降序。。)。顺手写一写题解,加深印象。
BZOJ 1103 : [POI2007]大都市meg
给一棵树,每次可以把树上的一些边标记了,问一个点与根之间需要走多少没有标记的边。
这个可以把这颗树遍历得到一个dfs序每第一次经过一个点的时候记录为+1
,第二次经过一个点的时候记录为-1
,然后记录每个点第一次经过时在序列里的位置f[i]和第二次经过在序列里的位置l[i],对于查询(x)就是序列中一直到f[x]-1的前缀和,因为真正没走的那些边都+1 -1
消掉了,只剩下真正要统计的边了。对于每次标记(a,b) 设a < b 就是序列里 f[b]的位置-1,l[b]的位置+1,就相当于消掉了这条边。另外这道题得手写栈dfs,否则会爆栈。