P7246 手势密码

Alex_Wei · 2022-08-10 15:31:27 · 题解

P7246 手势密码

除 EI 外的其它所有题解并没有严谨地证明贪心结论，本题解作为补充。

一道 DP 与贪心相结合的好题。

考虑树形 DP，设 b_i 表示将 i 子树所有节点权值清零的最小代价。

根据贪心思想，我们希望让尽量多的路径以 i 为一端，这样它们可以选择继续向上延伸，或者封闭在子树内。根据决策包容性可证。问题在于如何平衡最小代价 b_i 和以 i 为一端的路径条数 f_i。

可以猜到这样一条结论：在 b_i 最小的前提下使得 f_i 最大，接下来 f_i 每增大 1，b_i 至少增加 1，我们将看到这是不优的。其证明在最后给出。

考虑 u 及其所有子节点 v，如果它们分别独立，则总代价将为 b_u = a_u + \sum b_v，而我们可以执行以下两种操作减小 b_u：

• 选择 v_1\neq v_2，将 a_u, f_{v_1}, f_{v_2} 同时减去 1，并将总代价 b_u 减少 2，表示通过 u 将两条分别以 v_1 和 v_2 为端点的链相连。
• 选择 v，将 a_u, f_v 同时减去 1，并将总代价 b_u 减少 1，表示将 u 和一条以 v 为端点的链相连。

不妨先执行所有操作 1，再执行所有操作 2。设 S 为当前 \sum f_v，我们有以下几个容易证明的观察：

• 操作 1 执行完毕后，操作 2 执行的最大次数为 \min(a_u, S)。
• 根据摩尔投票法和经典结论，操作 1 执行的最大次数为 Q = \min(a_u, \lfloor \frac S 2 \rfloor, S - \max f_v)。

结合观察 1 与观察 2，因为操作 1 使得 a_u 减少 1，S 减少 2，因此当 S \leq a_u 时，一次操作 1 将减少两次操作 2，尽管总代价减小的值相同，但操作 1 执行次数增加，违背了最大化 f_u 的目标。否则 S > a_u，一次操作 1 仅减少一次操作 2，总代价减小的值增加了，更优。

进一步地，可以计算得出操作 1 执行次数 P = \min(Q, \max(0, S - a_u))，继而得到 f_u = a_u - P，b_u = a_u + \sum b_v - 2P - \min(f_u, S - 2P)，注意这里 S 为初始 \sum f_v。

对上述过程应用之前的结论，因为 f_v 每增加 1，b_v 都至少增加 1，但观察 P 的计算式，其显然最多只能让 P 增加 1，因此 b_u 不会变小。也就是说，增加代价以增加以 i 为一端的向上传递的链数不使得答案变优。

那么如何证明这一结论呢？也很容易：f_u 加 1 说明操作 1 执行次数减少 1，只需对 求解 f_u 时 操作 1 执行的最终态说明每撤销一次操作 1 均使得 b_u 增大即可：

• 若 a_u\leq S，每撤销一次操作 1 使得 \min(a_u, S) 即操作 2 次数增加 1，但 b_u 增加 2，不优。
• 若 a_u > S，必然没有执行任何一次操作 1，否则撤销一次操作 1 使得 b_u 不变，f_u 增加 1，与 f_u 的最大性矛盾。因此 f_u 已经取到最大值 a_u，无法增大。

综上，时间复杂度 \mathcal{O}(n)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
bool Mbe;
constexpr int mod = 1e9;
constexpr int N = 3e6 + 5;
int seed;
int Rand(int x) {
  seed = (1ll * seed * 0x66CCF + 19260817) % x + 1;
  seed = (1ll * seed * 0x77CCF + 20060428) % x + 1;
  seed = (1ll * seed * 0x88CCF + 12345678) % x + 1;
  seed = (1ll * seed * 0x33CCCCFF + 10086001) % x + 1;
  return seed;
}
int cnt, hd[N], nxt[N], to[N];
void add(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;}
int op, n, dn, a[N], id[N], fa[N];
ll f[N];
void dfs(int x, int ff) {
  fa[x] = ff, id[++dn] = x;
  for(int i = hd[x]; i; i = nxt[i]) if(to[i] != ff) dfs(to[i], x);
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin >> op;
  if(op == 1) {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      add(u, v), add(v, u);
    }
    dfs(1, 0);
  }
  else {
    cin >> seed >> n;
    for(int i = 1; i <= n; i++) a[i] = Rand(mod), id[i] = i;
    for(int i = 2; i <= n; i++) add(fa[i] = Rand(i - 1), i);
  }
  ll ans = 0;
  for(int _ = n; _; _--) {
    int x = id[_];
    ll sumf = 0, mxf = 0;
    for(int i = hd[x]; i; i = nxt[i]) {
      int y = to[i];
      if(fa[x] == y) continue;
      sumf += f[y], mxf = max(mxf, f[y]);
    }
    ans += a[x];
    ll P = min((ll) a[x], min(sumf / 2, sumf - mxf));
    P = min(P, max(0ll, sumf - a[x]));
    f[x] = a[x] - P, ans -= 2 * P + min(f[x], sumf - 2 * P);
  }
  cout << ans << "\n";
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/8/9
Author: Alex_Wei
start coding at 10:45
finish debugging at 19:39
*/