mengbierr

一个蒟蒻的博客

3月16

Codeforces 891C. Envy

题目大意

给出一个n个点m条边的无向图,每条边有边权,共Q次询问,每次给出 条边,问这些边能否同时在一棵最小生成树上。

题解

大力LCT,就是查询路径最大值是否与当前边相等,注意不要删掉询问里的边。

(其实这题正解是离线加并查集,但是是LCT裸题于是写了一发,加了些鬼畜优化就过了…)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注