BZOJ3712 [PA2014]Fiolki 重构树+并查集 杂题

BZOJ3712 [PA2014]Fiolki 重构树+并查集

又是一道思路非常好的题目。考虑到每个反应最多只进行一次,每个瓶子也只能往外倒一次,我们可以把每个瓶子想成一棵树。初始时,所有节点都是根节点,构成森林,每操作一次,就将两个瓶子表示的节点合并起来,可以用并查集维护,合并后的点重新标号,成为原来两个点的父节点,从下往上建树。注意到当两个物质能发生反应时,···