2286: [Sdoi2011]消耗战

题目链接

学了一下虚树。讲讲建虚树的方法。

首先把关键点按dfs序排序,假设y是x和y的lca则x必然可以省去,然后考虑维护一个栈,对于新加入的点x,设栈顶元素为y,f=lca(x,y),那么y到f的路径上的点就可以被压缩,然后把f和x入栈。最后把栈清空。

 

发表评论

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