传送门(yzhx在写这篇题解的时候bzoj崩了,只能挂这个了)
给定一颗 n 个点的树, 求最少链覆盖,以及使在最少链覆盖的前提下最长链最短
根据贪心的思想考虑每一个非树根节点,
显然它可以选择一条连向儿子的边归为连向父亲的边所在的那条链
(儿子数为奇数时必须选一条,偶数时可以不选,但其实这在第一问不重要),
所以每个非树根节点的贡献是 儿子数量/2,
而根节点若儿子数量为奇,则必须多生成一条链
也就是 (儿子数量+1)/2
原文：https://www.cnblogs.com/yzhx/p/11738313.html