【题解】牛客OI周赛15-提高组精

环球旅行

题意就是给出一棵带边权的树。删除上面的一条边，使分成的两棵树中较大的直径尽量小。求该直径。

【20分做法】

枚举删除哪条边，计算直径。复杂度 $O(n^2)$

【30分做法】

对于菊花图，删除最长边即可。

【40分做法】

对于一条链， $O(n)$ 枚举删边，可以直接算出剩下两条链的直径。

【60分做法】

对于 $n\le10^5$ 且数据随机的部分，答案肯定是删除直径上的某条边。随机数据树的直径不会很长，所以只枚举删除直径上的边。计算剩下的最长直径即可。

【100分做法】

将直径扯平。从左向右依次计算删除上面某条边后左边子树的直径。
图片说明
如图，删除红色边之后，左边子树的直径就是max(删除蓝色边时的答案，经过x但不经过y的最长链+蓝色边长度+y子树中与y相连的最长链长度)。
用同样的方法从右往左依次计算删除某条边后右边子树的直径。然后就可以统计出删除每条边之后的代价。
我们直接分别以直径的两个端点为根，用树形dp的方法求出每棵子树的直径。最后统计一遍答案即可。

恢复数列

【30分做法】

爆搜

【50分做法】

出题人也不知道怎么写233，但是鉴于这是OI赛制，就留给选手发挥吧。

【100分做法】

首先有一个结论：原题有解的充要条件是 $(x-1)|(n-2)$ 。这个的证明放到后面。
题目保证有解，所以全部数据都是满足这个性质的。
设 $n-2=k(x-1)$ 。
有一种可行的构造方法是让 $a_1=$ k。然后在 $a_2,a_3···,a_n$ 中，取 $x$ 个为 $0$ , $x-1$ 个为 $1$ , $x-1$ 个为 $2···x-1$ 个为 $k-1$ 。
这样左侧就是 $x+(x-1)(x^1+x^2+···+x^{k-1} )=x+(x-1)×\frac{x(x^{k-1}-1)}{x-1}=x^k$
恰好等于右侧。
关于上方结论的证明：
对原式两边 $mod(x-1)$ ，得到一个必要条件为 $1^{a_1}≡\sum\limits_{i=2}^n1^{a_i}(mod~ x-1)$
即 $1≡n-1(mod~x-1)⇒n-2≡0(mod ~x-1)⇒(x-1)|(n-2)$
再加上上方的构造方法，可以得出 $(x-1)|(n-2)$ 是原式有解的充要条件。