日记和二叉搜索树

题解

题意简述

给一棵有根树的每一个节点赋一个不同的权值 $w_i$，使得满足 $w_u < w_{\operatorname{lca}(u, v)} < w_v$ 的点对数最多。

显然，由于我们只关心大小关系，每个节点权值不同等价于权值是一个排列。

知识点

二叉搜索树、0-1 背包、多重背包、（可选）STL 模板

解题思路

$n \leq 10$

考虑暴力枚举每个节点的权值。

期望得分：8

保证儿子节点个数不超过 2

考虑贪心。首先，题目名称已经给了足够多的提示：二叉搜索树。回忆一下二叉搜索树的结构，对一个节点 $u$，其满足 $w_{\mathrm{lson}_u} < w_u < w_{\mathrm{rson}_u}$，因此 $\operatorname{lca}$ 为 $u$ 的贡献即为 $\mathrm{size}_{\mathrm{lson}_u} \times \mathrm{size}_{\mathrm{rson}_u}$。

但这不一定是最优的，我们需要证明。

试证：若一个节点的儿子个数为 2，钦定 一个子树权值 < 此节点权值 < 另一个子树权值 是最优的。

证明：先考虑 LCA 为此节点这部分贡献。此时，一对点 $(u, v)$ 产生贡献的必要不充分条件是它们分属两个子树。若钦定 一个子树权值 < 此节点权值 < 另一个子树权值，分属两个子树的任意一对点都会产生贡献，因此一定是最优的。

再考虑两子树内部的贡献。由于我们只考虑大小关系，子树与外部是独立的。

再考虑儿子个数为 1 的情况。这种情况下，任意钦定都不会产生额外贡献。

儿子个数为 0 的情况显然不需要讨论。

---

至此，我们得到了儿子节点个数不超过 2 时的最优构造。

期望得分：24

$n \leq 5000$

继续考虑贪心。

试证：当一个节点的儿子个数超过 2 时，将这若干个子树分成两部分，钦定 第一部分权值 < 此节点权值 < 第二部分权值 是最优的。额外地，这两部分的总大小越接近，构造越优。

证明：第一个命题可套用上述证法。第二个命题，考虑设两部分大小之和为 $s$，第一部分大小为 $a$，则我们要最大化 $a(s-a)$。显然 $a=(s-a)=\dfrac{s}{2}$ 时表达式取最大值，且值随 $|a-(s-a)|$ 的增大而增大。

这个结论如何用于贪心呢？我们相当于控制一部分大小 $\leq \dfrac{s}{2}$，并最大化这个大小。这可以化归到 0-1 背包问题，可以解决。

时间复杂度：$O(n^2)$，跑不满。

期望得分：44，实现得好并且加上各种特判有机会拿到 64

保证儿子节点个数不超过 3/4

节点个数不超过 3 时，使最大的一个单独成组是最优的，因此可以特判掉。

节点个数不超过 4 时，暴力枚举大概率会比背包跑得快，所以可以换成暴力。

期望得分：60~80。

保证树高不超过 10

这里说一个乱搞想法。树高不高，想塞下 $10^6$ 个节点，必然会有一堆大小重复的子树。

考虑多重背包的二进制优化。对 $c$ 个大小为 $k$ 的子树，我们只需要对若干个 $k \times 2^x$ 形式的东西（以及一个余项，具体可以搜多重背包了解）执行转移，而不需要对 $c$ 个 $k$ 进行转移。

这样会跑的快些。

期望得分：68~88。

$n \leq 30000$

考虑优化。0-1 背包中，我们只需要知道一个值是否能取到，之后暴力从大往小查找即可。而选择一棵大小为 $k$ 的子树，就相当于让每个值 $a$ 对 $a+k$ 产生贡献。

这是否让你想到了什么数据结构？bitset！

我们要维护的相当于是 operator <<, operator |, _Find_last。前两个操作 bitset 原生支持，第三个呢？bitset 是有 _Find_first 操作的，因此可以把整个序列翻转着存进 bitset 里，再用 _Find_first 实现。

如果你对 bitset 不够了解，也可以手写。这几个操作写起来都不算很难。

期望得分：88。

bitset 倍增优化

如果对每个节点 DP 时，都维护一个 $10^6$ 的 bitset，是会直接 TLE 的。

如果你手写 bitset，不会有这个问题。但如果你在用 STL，就不得不解决它了。

出题人的写法是模板元编程，利用 template <int mx> solve() 来解决这个问题，每次执行 solve 时，若当前的 mx 还不够大，就调用 solve<mx * 2>()，否则就开一个大小为 mx 的 bitset 并做背包。

这里有一个小问题：子树大小并非编译期确定，因此编译器会不断倍增 mx，直到溢出。可以在 mx * 2 时将其与 1048576 或一个足够大值取 min。

倍增优化的替代

如果你不会元编程，也不想手写，那么可以考虑“根号分治”。

伪代码如下：

if (siz[u] <= 10) solve10();
else if (siz[u] <= 100) solve100();
else if (siz[u] <= 1000) solve1000();
else if (siz[u] <= 10000) solve10000();
else if (siz[u] <= 100000) solve100000();
else solve1000000();

它实际上与元编程进行了相近的工作。但是这样写，你需要将 solve 函数复制若干遍，并调整内部 bitset 的大小，非常麻烦。

元编程事实上就是让编译器完成这一工作，减少码量。

再提多重背包

这样大部分情况是正确的了。但是菊花图和类似的东西仍然能卡飞你的程序。此时多重背包二进制优化就显得十分有效了。

复杂度不会证，反正应该能过。

期望得分：100。

标准代码

C++

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int n, a[maxn], deg[maxn];
struct Edge {
  int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void add(int u, int v) {
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}

int siz[maxn];
long long dp[maxn];
vector<int> s[maxn], t;
template<int mx>
long long solve(int sz) {
  if (mx < sz + 5) {
    return solve<((mx << 1) > 1048576 ? 1048576 : (mx << 1))>(sz);
  } else {
    bitset<mx + 5> vis;
    vis.set(mx);
    for (auto i : t) vis |= (vis >> i);
    int mid = (sz - 1) / 2;
    int i = vis._Find_next(mx - mid - 1);
    return 1ll * (mx - i) * (sz - 1 - (mx - i));
  }
}
void make(vector<int> &a) {
  sort(a.begin(), a.end());
  a.emplace_back(-1);
  t.clear();
  int cnt = 1;
  for (int i = 1; i < a.size(); ++i) {
    if (a[i] != a[i - 1]) {
      long long x = a[i - 1], j = 1;
      while (j < cnt) {
        t.emplace_back(x * j);
        cnt -= j;
        j <<= 1;
      }
      t.emplace_back(x * cnt);
      cnt = 1;
    } else ++cnt;
  }
}
void dfs(int u, int fa) {
  siz[u] = 1;
  int son = 0, mx = 0;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs(v, u);
    siz[u] += siz[v];
    dp[u] += dp[v];
    s[u].push_back(siz[v]);
    mx = max(mx, siz[v]);
    ++son;
  }
  if (siz[u] == 1) {
    s[u].clear();
    return;
  } else if (son == 1) {
    s[u].clear();
    return;
  } else if (son == 2) {
    dp[u] += 1ll * s[u][0] * s[u][1];
    s[u].clear();
    return;
  }
  int mid = (siz[u] - 1) / 2;
  if (mx >= mid) {
    dp[u] += 1ll * mx * (siz[u] - 1 - mx);
    s[u].clear();
    return;
  }
  make(s[u]);
  dp[u] += solve<8>(siz[u]);
  s[u].clear();
  return;
}

int main() {
  //freopen("bst.in", "r", stdin);
  //freopen("bst.out", "w", stdout);

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    ++deg[u], ++deg[v];
    add(u, v);
    add(v, u);
  }
  int chain_border = 0, leaf = 0;
  for (int i = 1; i <= n; ++i) {
    if (deg[i] == 1) {
      ++chain_border;
      if (chain_border == 2) leaf = i;
    } else if (deg[i] != 2) {
      chain_border = -1;
      break;
    }
  }
  if (chain_border != 2) dfs(1, 0);
  cout << dp[1] << '\n';
  // for (int i = 1; i <= n; ++i) clog << dp[i] << ' ';
  
  cout.flush();
  return 0;
}