Codeforces Round #720 (Div. 2) D. Nastia Plays with a Tree 题解

一、算法分析
基本算法是树上统计+贪心。笔者参赛时是不会做的，后来参考了洛谷too_late 的博客 的 https://www.luogu.com.cn/blog/115857/solution-cf1521d题解才码出这道题。下面简单地描述一下思路：
1.划分链的种类，可以将链划分为1号链和2号链。
2.对于每个子树，最好的情况是能保留成1个1号链，或1个二号链。所以对于一棵子树，设子树的根结点为u，u的子结点为集合{v}，则对于所有的v，其可能是1号链的根结点（记为1号v）或2号链的根结点（记为2号v）。然后分情况讨论：
（1）只有一个1号v，则带上u作为一个1号链保留（作为主链）。
（2）只有两个1号v，则带上u作为一个2号链保留（作为主链）。
（3）有大于等于3个1号v，则将其中两个作为2号链保留（作为主链），剩下的接在2号链的某一边的下面。
（4）在1~3的情况下存在2号v，则将2号v整

Codeforces Round #720 (Div. 2) D. Nastia Plays with a Tree 题解最先出现在Python成神之路。