有没有一种可能，我其实是一个伞兵，离了队友啥都不会，但我的队友离了我反而更猛了？
E
队长给的做法是先随便找一个非叶子结点作为根，然后假设整棵树的和是 $s$，深度为 $1$ 的结点子树和是 $t$，那么就能推出除了根节点之外偶数深度的子树和都是 $s – t$，奇数深度的都是 $t$，进而推出每个点的点权和 $s, t$ 的关系。然后进一步发现令 $s = 1$ 或者 $t = 1$ 都是有解的。
题解的做法比较神奇，是黑白染色之后白点权值设为度数，黑点权值设为负的度数。不难证明这样搞之后每次划分的若干子树和都是 $1$ 或者 $-1$。
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 100005;
vector<int> G[maxn];
int pr[maxn];
int a[maxn], b[maxn];
int d[maxn];
void dfs(int x) {
if (pr[x])
d[x] = d[pr[x]] + 1;
for (int y : G[x])
if (y != pr[x]) {
pr[y] = x;
dfs(y);
}
int cnt = (int)G[x].size() - (bool)pr[x];
// odd 1
// even s - 1
if (!(d[x] & 1)) {
a[x] = 1;
b[x] = -1 - cnt;
if (!pr[x])
b[x]++;
}
else {
a[x] = -cnt;
b[x] = 1 + cnt;
}
}
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
int r = 0;
for (int i = 1; i <= n; i++)
if ((int)G[i].size() > 1) {
r = i;
break;
}
dfs(r);
set<int> st;
for (int i = -n; i <= n; i++)
st.insert(i);
for (int i = 1; i <= n; i++) {
int u = a[i], v = b[i];
if (u) {
if (abs(v) % abs(u) == 0)
st.erase((-v) / u);
if (u > 0) {
while ((long long)u * *st.begin() + v < -100000)
st.erase(*st.begin());
while ((long long)u * *st.rbegin() + v > 100000)
st.erase(*st.rbegin());
}
else {
while ((long long)u * *st.begin() + v > 100000)
st.erase(*st.begin());
while ((long long)u * *st.rbegin() + v < -100000)
st.erase(*st.rbegin());
}
}
}
int x = *st.begin();
for (int i = 1; i <= n; i++) {
cout << a[i] * x + b[i];
if (i < n)
cout << ' ';
else
cout << '\n';
}
for (int i = 1; i <= n; i++) {
G[i].clear();
pr[i] = 0;
d[i] = 0;
a[i] = b[i] = 0;
}
}
return 0;
}F
$a_i a_j + t(a_i + a_j)$ 对 $a_j$ 的偏导是 $a_i + t$，换言之是线性的，所以如果固定 $a_j$，显然 $a_i$ 依 $a_i + t$ 的正负不同只有可能连接 $a_i$ 最小的或者最大的。而两个最值中间肯定也有一条连边，所以直接就构造出了最小生成树。
把 $a_i$ 排个序之后发现直接按顺序扫就行了，只有当 $t = -a_i$ 的时候最小生成树才会变动一条边。维护一下 $f(t) = kt + b$ 即可，判一下 $t = -a_n$ 和 $t = -a_1$ 时的斜率即可区分出无界的情况。
（这题也太伞兵了，为什么我会连直接构造最小生成树都想不到啊。。）
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 200005;
int a[maxn];
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
long long k = 0, b = 0;
for (int i = 1; i < n; i++) {
k += a[i] + a[n];
b += (long long)a[i] * a[n];
}
bool inf = k < 0;
long long ans = k * a[1] + b;
for (int i = n - 1; i > 1; i--) {
k -= a[n];
k += a[1];
b -= (long long)a[i] * a[n];
b += (long long)a[i] * a[1];
ans = max(ans, k * -a[i] + b);
}
inf |= k > 0;
if (inf)
cout << "INF\n";
else
cout << ans << '\n';
}
return 0;
}G
挺妙的一个构造，思想实际上就是先构造出有多个环的排列，然后利用回文 $i$ 和 $n – i + 1$ 位置相等的性质把所有环进行合并。题解的做法是一次全部合并，不过我猜测两两合并也是可行的。（也许这个可以解释为什么最后一步合并和其他步骤不太一样。）
不过还没有完全理解，有空要再看看题解。
CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) Editorial – Codeforces
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 200005;
int ufs[maxn];
int findufs(int x) {
return x == ufs[x] ? x : (ufs[x] = findufs(ufs[x]));
}
void link(int x, int y) {
ufs[findufs(x)] = findufs(y);
}
vector<int> v[maxn];
int a[maxn], p[maxn], c[maxn];
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
v[a[i]].push_back(i);
}
bool bad = (count_if(v + 1, v + n + 1, [] (const auto &v) {return (bool)(v.size() & 1);}) > n % 2);
if (n & 1)
bad |= ((int)v[a[n / 2 + 1]].size() == 1);
if (bad) {
for (int i = 1; i <= n; i++)
v[i].clear();
printf("NO\n");
continue;
}
if (n & 1) {
int k = 0;
for (int i = 1; i <= n; i++)
if ((int)v[i].size() & 1) {
k = i;
break;
}
if (v[k].back() == n / 2 + 1)
swap(v[k].back(), v[k][(int)v[k].size() - 2]);
p[n / 2 + 1] = v[k].back();
v[k].pop_back();
}
for (int i = 1, k = 1; i <= n / 2; i++) {
while (v[k].empty())
k++;
p[i] = v[k].back();
v[k].pop_back();
p[n - i + 1] = v[k].back();
v[k].pop_back();
}
for (int i = 1; i <= n; i++)
ufs[i] = i;
for (int i = 1; i <= n; i++)
link(i, p[i]);
for (int i = 1; i <= n / 2; i++)
if (findufs(i) != findufs(n - i + 1)) {
swap(p[i], p[n - i + 1]);
link(i, n - i + 1);
}
for (int i = 1; i <= n; i++) {
if (n % 2 && i == n / 2 + 1)
continue;
if (!c[findufs(i)])
c[ufs[i]] = i;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
cnt += (i == findufs(i));
if (true || cnt > 1) {
pair<int, int> pr;
int k = 0;
for (int i = 1; i <= n; i++)
if (c[i]) {
pair<int, int> t(p[c[i]], p[n - c[i] + 1]);
if (k) {
p[c[i]] = pr.second;
p[n - c[i] + 1] = pr.first;
}
k = c[i];
pr = t;
}
for (int i = 1; i <= n; i++)
if (c[i]) {
p[c[i]] = pr.first;
p[n - c[i] + 1] = pr.second;
break;
}
}
printf("YES\n");
for (int i = 1; i <= n; i++)
printf("%d%c", p[i], i < n ? ' ' : '\n');
for (int i = 1; i <= n; i++) {
v[i].clear();
c[i] = 0;
p[i] = 0;
ufs[i] = 0;
}
}
return 0;
}
不是说多刷刷cf的题吗，这是怎么会事呢
因为有鸽子，甚至鸽了一天才看博客（