C
假设我们已经确定了匹配集合\(S,|S|=x\)
考虑剩下的位置,考虑能变换的最小匹配数
令\(num\)为最大颜色的个数
最小匹配数为\(max(0,2*num-(n-x))\)
那么让\(num\)尽量小即可
D
令蛇长\(L\)
令某个点为关键点,满足该点有三个大于等于\(L\)的分支,我们可以利用关键点让蛇翻转
结论1:若蛇某端点能到达一个关键点,则能到达所有关键点
结论2:若蛇到达不了关键点,则不能实现翻转
证明:
考虑树上的直径,若蛇不能到达直径,可以把直径删掉,取蛇所在连通块,显然这并不影响答案
若蛇能到达直径,我们可以证明其永远不能离开,若能离开,则显然图中会存在关键点
若蛇当前在直径,则不能离开,显然不能翻转;若蛇不在直径,与蛇能到达直径矛盾
我们找到图中任意关键点\(root\),以其作为根
将蛇移动,若能使端点互为祖先关系,则可以到达\(root\)
令端点为\((a,b)\),选择一端点作为起始点
起始点往下走到能前往的最深的叶子节点,另一端往下走到能前往的最深叶子节点,反复交替,知道互为祖先
可以用倍增或长链剖分来模拟这个过程