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 本质相同，于是直接搬过来即可。