[CF 1076E] Vasya and a Tree

思路 在每个节点上挂两个std::vector<int>,分别记录当前节点上的修改的深度和权值,DFS一下,用一个BIT维护当前时刻每个深度上的修改,进入子树的时候用BIT修改,出子树的时候还原 […]

[APIO2010]巡逻

Luogu P3629 bzoj 1912 思路 首先考虑$K=1$的情况,很显然,连一条边之后,这条边所连接的两个原树上的点都只需要走一次,所以把这棵树的直径的两端连接起来是最优的。 考虑$K=2$ […]

[bzoj 4668]冷战

bzoj 4668 思路 小水题 将并查集当做树来看待,点$x$与$x$的父亲之间的边权为这条边的产生时间,那么$x$和$y$最早出现在同一个集合的时间就是$x$到$y$路径上的最大边权。 为了限制树 […]