回归梦想的博客

P4381 [IOI2008]Island

P4381 [IOI2008]Island 题意：给你一棵基环树森林，求出基环树的直径之和. 题解：对于基环树,我们将环看作根,那么直径有两种情况:: 1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可; 2.经过环,答案就是i的子树内长度+j的子树内长...

P2607 [ZJOI2008]骑士

P2607 [ZJOI2008]骑士题意： n个点n个边，每个点都有权值，相邻的点不能同时选择，问如何选择能使得权值最大题解：这个题很有P1352 没有上司的舞会这个题的感觉，唯一的区别是那个题保证是树，而本题肯定不是树，而是基环树也就是本题中，每一个连通块有且只有一个环，所以我们找到这个环并...

P5049 [NOIP2018 提高组] 旅行

P5049 [NOIP2018 提高组] 旅行题意：一棵树(可能是基环树)，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。 1≤n≤500000 m=n−1 或 m=n 题解：如果不是基环树，那直接每次走字典序小的点即可对于基环树：第一个方法：暴力删边将基环...

基环树

@[toc]参考博客概念基环树 = n个点n条边的图 = 1棵树 + 1个环无向树(N点N边无向图) 外向树(每个点入度=1) 内向树(每个点出度=1) 以上三种树有十分优秀的性质，就是可以直接将环作为根。就可以对每个环的子树进行单独处理，最后再处理环找环拓扑排序处理无向图可以找出环...