Color a Tree
好不可做？可以尝试一下DP贪心网络流。DP 似乎没法做，网络流也不太行，所以试一下贪心。
考虑全局中最大权值的那个点，如果它没父亲，那么一定会先选它；否则，选完它父亲就一定先选它。于是我们可以把它缩成一个点。
但是我们并不知道缩点后的权值是多少，这样就没法继续缩下去。我们考虑一对被缩点的父子 \(x,y\)，以及全局中的另一个点 \(a\)，什么时候会先选 \(a\),什么时候先选 \(x,y\)。如果先选 \(x,y\)，那么就有 \(x + 2y + 3a \le a + 2x + 3y\)，整理得 \(a \le \dfrac{x + y}{2}\)，即我们可以把点中的均值当作点权。
于是并查集 + 堆模拟即可。注意重载运算符时当均值相同时要比较其余变量，否则可删堆将出错。
struct node {
ll val, siz;
int cur;
bool operator <(const node a) const {
if (val * a.siz != siz * a.val) return val * a.siz < siz * a.val;
else if (val != a.val) return val < a.val;
else if (siz != a.siz) return siz < a.siz;
return cur < a.cur;
}
node operator +(const node a) const {
memo += siz * a.val;
return (node){val + a.val, siz + a.siz, cur};
}
bool operator ==(const node a) const { return cur == a.cur && val == a.val && siz == a.siz; }
}ans, tmp[N];
struct Heap {
priority_queue<node> q, w;
inline node top() { while (w.size() && q.top() == w.top()) q.pop(), w.pop(); return q.top(); }
inline void del(node x) { w.push(x); }
inline void push(node x) { q.push(x); }
inline int size() { return q.size() - w.size(); }
}hp;
int v[N];
int fa[N];
bool vis[N];
int find(int cur) { return fa[cur] == cur ? cur : fa[cur] = find(fa[cur]); }
int main() {
int n, r;
read(n), read(r);
ans = (node){0, 0, 0};
while (n || r) {
memo = 0;
for (register int i = 1; i <= n; ++i) read(v[i]), tmp[i] = (node){v[i], 1, i}, hp.push(tmp[i]), fa[i] = i;
for (register int i = 1; i < n; ++i) {
int u, v; read(u), read(v); fath[v] = u;
}
while (hp.size()) {
node nd = hp.top(); hp.del(nd);
int rt = nd.cur, faa = find(fath[rt]);
if (!faa || vis[faa]) { ans = ans + nd; vis[rt] = true; continue; }
hp.del(tmp[faa]);
tmp[faa] = tmp[faa] + tmp[rt]; fa[rt] = fath[rt];
hp.push(tmp[faa]);
}
printf("%lld\n", memo + ans.val);
ans = (node){0, 0, 0};
while (hp.q.size()) hp.q.pop();
while (hp.w.size()) hp.w.pop();
for (register int i = 1; i <= n; ++i) fath[i] = 0, vis[i] = false;
read(n), read(r);
}
return 0;
}
排列
题意较为难懂，可以理解成，如果第 \(i\) 个数跑到了第 \(j\) 个位置，那么 \(j\) 及之前的位置就都不能有 \(a\) 值为 \(i\) 的数。换句话说，值为 \(i\) 的数能够出现，当且仅当第 \(i\) 个数已经出现。
题意转化以后就比较好做了。我们可以把这种限制关系用边来表示一下，结果应该是基环树森林。显然如果有环一定无解，那么结果是森林。然后再看最小化的那个值，发现实际上和 Color a Tree 本质相同，于是直接搬过来即可。