http://codeforces.com/contest/438

A题
考虑删除点的顺序,从点的大的往小的删除,然后考虑边的删除,我们会发现每条边对结果的“贡献”都是

B题
采用“边建图边计算”的方式。
依旧以边为主,首先对边按照min(a[u], a[v])递减排序,然后按此顺序加边,即用并查集动态维护连通分量。
由于边是按照min(a[u], a[v])递减排序的,所以两个连通分量上之间的连线所产生的“贡献”必为min(a[u], a[v]) * num[find(u)] * num[find(v)](根据乘法原理,以及这条边是桥),连通分量内的连线不产生贡献(因为不会经过)。

D题
如何处理操作2?
注意到若m<=a,则a%=m使a至少削减一半,所以这题维护区间和值以及区间最值,暴力完成操作2即可AC。

Comments

comments powered by Disqus