转载请注明出处:http://tokitsukaze.live/

题目链接:https://codeforces.com/gym/102012


Solved:2/13。

 

A.Rikka with Minimum Spanning Trees

数据是随机生成器生成,边权相同的概率无限接近于0。所以直接跑一次最小生成树即可。

注意:特判不存在生成树的情况,输出0。

 

G.Rikka with Intersections of Paths

考虑到去重,容斥,都是不存在的。那么只能每次加进一些链,计算增加的贡献。想到这基本就会做了。

统计一个节点被覆盖了几次,用树上差分做,记为cnt[]。

然后统计增加的链数,在lca处进行标记,记为tag[]。

那么dfs到节点x,新增加的链的贡献就是C(cnt[x],k)-C(cnt[x]-tag[x],k)。

 

 

 

代码:

https://github.com/tokitsu-kaze/ACM-Solved-Problems/tree/master/gym/2018-2019%20ACM-ICPC%2C%20Asia%20Xuzhou%20Regional%20Contest