Codeforces Round 720

题目

https://codeforces.com/problemset/problem/1521/D

评分2500

题意

给你树

每次拆一条边,连两个点

用最小操作次数让树的形状变成链状

求具体方案

样例1e4组,每个数节点小于1e5,所有节点数小于2e5

过程中没有限制一定要保持是树

题解

拆与合并互不干扰,也不会因为顺序干扰,

如果先拆完再合并,合并就很easy,因为拆分出的每个联通块一定是链状.

那问题是怎么拆分

要拆的节点明显是,连接数大于3,任取一个节点为根, 计算每个节点深度,深度从大到小,那么一条点要拆边,一定是和它父节点拆(贪心性质), O(n)

无代码

评价

这题最有意思的地方在于,不是正确方法需要很复杂的思路,而是你能想到许许多多不正确的看似时间内的做法,

比如我考虑过

1. 多点-多点优先斷,连小于2的点. 问题:可能成环, 也可能不是最小覆盖
2. 任选根,连leaf,断公共祖先,递归处理,也存在重复断和断得小于1的问题
3. 找不重叠的链,断了后连:

1-2-3-4-5
    |
6-7-8-9-0

问题 非主链,和存在非连接链, 难找断开位置.

4. +多点优先

  1      3
  |      |
  2------4
  |      |
5-6-7  8-9-0

问题: 多点成链, 2次更优,可能找到非最小

等等错误的思路干扰