夢に僕らで帆を張って
来るべき日のために夜を超え

标签 基环树 下的文章

September 26, 2019

洛谷P2607/ZJOI2008 骑士

题意:求基环树最大带权独立集。数据范围: $N \le 1000000$题解:算法:树形dp分析题意:由“每个骑士都有且仅有一个自己最厌恶的骑士(当然不是他自己)”建立有向图,将每个人 $x$ 最厌恶的人 $y$ 记为其父节点 $fa[x]=y$ ,可得每个节点有且仅有一条出边,且无自环。由于共有 $N$ 条边,所以该图为基环树。考虑到基环树的性质,删边后必定构成一棵树。分别以删去的边连接的...