回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共3篇）

P4381 [IOI2008]Island

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

ing **** 基环树

2021-02-22

0 665

P2607 [ZJOI2008]骑士

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

基环树树形dp ***

2021-02-22

0 613

P5049 [NOIP2018 提高组] 旅行

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

基环树 ***

2021-02-22

0 517