loj6900 & qoj6350

发表于 更新于 本文字数： 8k 阅读时长 ≈ 7 分钟

有一棵大小为 nn 的树，把 kk 个点染成黑色，一条边的权值为把它断掉后两个联通块黑点数量之差，求权值之和最小值。

n,k≤5×105n,k\le 5\times 10^5 。

有一棵大小为 nn ，边带权的树，再定义一个大小为 nn 的完全图，其中两点 (i,j)(i,j) 的边权为树上距离，求对于每个 k≤n/2k\le n/2，大小为 kk 的匹配的最大权值。

n≤106n\le 10^6 。

其实是同一个题，第二个问题容易发现选的匹配的交不为空，也就是可以选出一个重心。

问题都变成，选出一个根作为重心，选若干个黑点使得深度和最大，一个题是要求一个 kk 的答案，另一个是求所有 kk 为偶数的答案。

先考虑只有一个 kk 咋做，设 m=k/2m=k/2，我们可以选出一个根，然后把所有点深度排序，然后依次选，如果选了之后没有子树大小超过 mm 就合法，然后可以贪心得到一个方案。

得到一个方案之后，如果一个子树选的点数 <m<m，那么这个子树里面的点作为根肯定不优，证明的话考虑移动一格进来，外面的点距离都加一，但是只会加 mm，而里面的点距离也会减小 mm，而且可供选择的点变少了，显然不优。

由于最优方案一定有一个对应的重心，在这个重心找就可以得到答案。

但是注意 Alex_Wei 的题解中「考虑最优方案对应的黑点重心 x∗x^*，那么 x∗x^* 不会有子树希望选超过 mm 个黑点，否则调整可得更优解。」这句话并不对，因为最优方案可能有多个重心，比如对于一条链，k=2k=2，那么除了中间这个点之外，其他点做重心都会有一边希望选超过 mm 个点。

但是对于最优方案的任意重心，按上面的方法贪心填得到的答案一定是对的，因为这是这个点作为重心的最优方案。

然后我们大概得到了一个做法，就是选一个点做一遍贪心，然后找一个选了 mm 个点的子树，然后进入，递归，点分治即可。

但是发现在 kk 是偶数的时候是对的，但是 kk 为奇数的时候，可能会有两个子树选了 mm 个点，这样复杂度爆了。

然后来证明，kk 是奇数的时候，最优方案是 k−1k-1 的最优方案上加一个点。

考虑 k−1k-1 的时候的一个最优方案，如果是 xx 作为重心，相当于考虑是否会有其他点 yy 作为重心时，在 kk 的时候能超过 xx。

考虑如果 yy 在一个选的点数 <m<m 的子树中，那么移过来之后，外面 mm 个肯定选满，而里面选择的点变少了，而且权值变小，所以一定不优。

因此可选重心一定满足，这个点的子树内选了 mm 个点。

而对于这些点，由于外面选满，所以选前 k−1k-1 个点的方案一定和 xx 重合，因此直接加一个点即可。

加一个点的贡献是好计算的，考虑每条边的贡献即可，大概长这样。

TL5PIP3PY00MQ__C__78H.png

桶排，总复杂度 O(nlog⁡n)\mathcal O(n\log n) 解决了单个 kk 的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define V vector
#define Vi vector<int>
#define sz(a) ((int)a.size())
#define fi first
#define se second
#define Int pair<int, int>
#define ll long long
#define Inf ((ll)1e18)
#define pb push_back
#define ins insert
#define For(i, x, y) for (auto i = (x); i <= (y); i++)
#define Rep(i, x, y) for (auto i = (x); i >= (y); i--)
#define all(a) a.begin(), a.end()
#define IO(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
using namespace std;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int n, K, odd = 0;
  cin >> n >> K;
  if (K & 1) K--, odd = 1;

  V<Vi> e(n + 5);
  for (int i = 1, x, y; i < n; i++) cin >> x >> y, e[x].pb(y), e[y].pb(x);

  ll Ans = Inf;
  auto solve = [&](int rt) {
    V<V<Int>> mp(n + 5);
    auto dfs = [&](auto lf, int x, int fa, int r, int d) -> void {
      mp[d].pb({r, x});
      for (int y : e[x])
        if (y ^ fa) lf(lf, y, x, r, d + 1);
    };
    for (int y : e[rt]) dfs(dfs, y, rt, y, 1);

    Vi vis(n + 5), d(n + 5);
    ll ans = 1ll * (n - 1) * (K + odd);
    int now = 0, gg = 0;
    Rep(i, n, 0) {
      int ff = 0;
      for (auto [x, id] : mp[i]) {
        if (now < K) {
          if (vis[x] == K / 2) {
            ff = x;
            continue;
          }
          vis[x]++, d[id] = 1;
          ans -= 2 * i, now++;
        }
      }
      if (now < K && ff && !gg) gg = ff;
    }
    if (now < K) return gg;
    Ans = min(Ans, ans);
    if (odd) {
      Vi sum(n + 5);
      auto pre = [&](auto lf, int x, int fa) -> void {
        sum[x] = d[x];
        for (int y : e[x])
          if (y ^ fa) lf(lf, y, x), sum[x] += sum[y];
      };
      pre(pre, rt, 0);

      Vi dis(n + 5, -1);
      queue<int> q;
      For(i, 1, n) if (sum[i] >= K / 2) dis[i] = 0, q.push(i);
      for (; !q.empty(); q.pop()) {
        int x = q.front();
        for (int y : e[x])
          if (dis[y] < 0) dis[y] = dis[x] + 1, q.push(y);
      }
      int mx = 0;
      For(i, 1, n) if (!d[i]) mx = max(mx, dis[i]);
      Ans = min(Ans, ans - 2 * mx);
    }

    return gg;
  };
  Vi vis(n + 5), siz(n + 5);
  auto work = [&](auto lf, int u, int S) -> void {
    int mn = 1e9, rt = 0;
    auto get_rt = [&](auto lf, int x, int fa) -> void {
      siz[x] = 1;
      int mx = 0;
      for (int y : e[x])
        if (y != fa && !vis[y])
          lf(lf, y, x), siz[x] += siz[y], mx = max(mx, siz[y]);
      if (max(mx, S - siz[x]) < mn) mn = max(mx, S - siz[x]), rt = x;
    };
    get_rt(get_rt, u, 0);
    vis[rt] = 1;
    int t = solve(rt);
    if (vis[t] || !t) return;
    lf(lf, t, siz[t] > siz[rt] ? S - siz[rt] : siz[t]);
  };
  work(work, 1, n);
  cout << Ans << '\n';
}

然后来做求所有偶数的答案。

首先前面证明了偶数到奇数是增量的，同理可以证明所有 kk 都是增量的。

现在唯一的问题是，增量的贡献是难以维护的。

考虑加两个点会有啥情况：都选没到 mm 的子树，一个到了 mm，两个都到。

第一种无事发生，直接选离 xx 最远的两个点，第三种也简单，选两个最远的，然后把重心移过去，然后算一下贡献即可。

中间这种情况讨论一下，发现贡献也是 xx 到这两个点距离之和。

因此做法就简单了，每次找一个离 xx 最远的点加入，然后维护 xx 的移动使之还是重心，这样做在 kk 是奇数都时候贡献会算错，但是偶数的时候都是对的。

此时有一个很直接的做法是每次删点，维护直径，来找最远点，复杂度 O(nlog⁡2n)\mathcal O(n\log^2 n)。

为什么不能直接维护每个点到 xx 的距离？因为每次是删叶子，移动 xx 的时候有很多点贡献难以计算。

倒过来，kk 从大到小计算，相当于每次删距离最近的点，这样剩下没删的肯定是若干子树，而每次差为 11，xx 移动的路径上的子树里一定都是空的，所以贡献可以简单计算，复杂度变成 O(nlog⁡n)\mathcal O(n\log n)。

小卡常，需要使用树剖 LCA 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
#define V vector
#define Vi vector<int>
#define sz(a) ((int)a.size())
#define fi first
#define se second
#define Int pair<ll, int>
#define Inf ((ll)1e18)
#define pb push_back
#define ins insert
#define For(i, x, y) for (auto i = (x); i <= (y); i++)
#define Rep(i, x, y) for (auto i = (x); i >= (y); i--)
#define all(a) a.begin(), a.end()
#define IO(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
using namespace std;

#define ll long long
#define seg int p, int l, int r
#define lid p << 1, l, mid
#define rid p << 1 | 1, mid + 1, r
#define mid ((l + r) / 2)

const int N = 1e6 + 5;
Int mn[N * 4];
ll la[N * 4];

struct Ace_taffy {
  Ace_taffy(int n) {}

  void work(int p, ll z) { la[p] += z, mn[p].fi += z; }
  void pd(int p) { work(p << 1, la[p]), work(p << 1 | 1, la[p]), la[p] = 0; }

  void chg(seg, int x, ll z) {
    if (l == r) {
      mn[p] = {z, l};
      return;
    }
    x <= mid ? chg(lid, x, z) : chg(rid, x, z);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
  }
  void add(seg, int L, int R, ll z) {
    if (l >= L && r <= R) return work(p, z);
    if (la[p]) pd(p);
    if (L <= mid) add(lid, L, R, z);
    if (R > mid) add(rid, L, R, z);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
  }
  void del(seg, int x) {
    if (l == r) {
      mn[p].fi = Inf;
      return;
    }
    if (la[p]) pd(p);
    x <= mid ? del(lid, x) : del(rid, x);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
  }
};

struct Spade {
  Vi c;
  int n;
  Spade(int _n) : c(_n + 5) {
    n = _n;
    For(i, 1, n) add(i, 1);
  }

  void add(int x, int z) {
    for (; x <= n; x += x & -x) c[x] += z;
  }
  int ask(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans += c[x];
    return ans;
  }
  int ask(int l, int r) { return ask(r) - ask(l - 1); }
  int kth(int k) {
    int r = 0;
    Rep(i, __lg(n), 0) if (r + (1 << i) <= n && k > c[r + (1 << i)]) {
      k -= c[r + (1 << i)], r += 1 << i;
    }
    return r + 1;
  }
};

int siz[N], in[N], out[N], D[N], pos[N], ti = 0, rt = 0, n, sn[N], tp[N], f[N];
ll dep[N];
V<Int> e[N];

void pre(int x, int fa) {
  siz[x] = 1, in[x] = ++ti, D[x] = D[f[x] = fa] + 1, pos[ti] = x, sn[x] = 0;
  for (auto [y, z] : e[x])
    if (y ^ fa) {
      dep[y] = dep[x] + z, pre(y, x), siz[x] += siz[y];
      if (siz[y] > siz[sn[x]]) sn[x] = y;
    }
  if (max(siz[sn[x]], n - siz[x]) <= n / 2) rt = x;
  out[x] = ti;
}

void dfs(int x, int Tp) {
  tp[x] = Tp;
  if (!sn[x]) return;
  dfs(sn[x], Tp);
  for (auto [y, z] : e[x])
    if (D[y] > D[x] && y != sn[x]) dfs(y, y);
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n;
  for (int i = 1, x, y, z; i < n; i++)
    cin >> x >> y >> z, e[x].pb({y, z}), e[y].pb({x, z});
  pre(1, 0);
  ti = 0, dep[rt] = 0, D[rt] = 1;
  pre(rt, 0), dfs(rt, rt);

  auto lca = [&](int x, int y) {
    if (!x || !y) return 0;
    for (; tp[x] != tp[y]; x = f[tp[x]])
      if (D[tp[x]] < D[tp[y]]) swap(x, y);
    return D[x] < D[y] ? x : y;
  };

  auto jump = [&](int x, int y) {
    for (; D[f[tp[x]]] > D[y];) x = f[tp[x]];
    return tp[x] == tp[y] ? sn[y] : tp[x];
  };

  Ace_taffy tr(n);
  Spade tt(n);
  V<ll> Ans(n + 5);
  ll res = 0;
  For(i, 1, n) tr.chg(1, 1, n, in[i], dep[i]), res += dep[i];
  if (!(n & 1)) Ans[n / 2] = res;

  Rep(i, n - 1, 2) {
    Int T = mn[1];
    res -= T.fi, tr.del(1, 1, n, T.se);
    tt.add(T.se, -1);

    auto move = [&](int p) {
      tr.work(1, dep[p] - dep[rt]);
      int T = dep[p] > dep[rt] ? p : rt;
      tr.add(1, 1, n, in[T], out[T], 2 * (dep[rt] - dep[p]));
      res -= abs(dep[p] - dep[rt]);
      rt = p;
    };

    if (tt.ask(in[rt], out[rt]) * 2 < i) {
      int x = pos[tt.kth(tt.ask(in[rt] - 1))];
      int y = pos[tt.kth(tt.ask(out[rt]) + 1)];
      x = lca(x, rt), y = lca(y, rt);
      move(D[x] > D[y] ? x : y);
    }

    int y = pos[tt.kth((tt.ask(in[rt]) + 1 + tt.ask(out[rt])) / 2)];
    if (y != rt) {
      y = jump(y, rt);
      if (tt.ask(in[y], out[y]) * 2 > i) {
        int L = pos[tt.kth(tt.ask(in[y] - 1) + 1)];
        int R = pos[tt.kth(tt.ask(out[y]))];
        move(lca(L, R));
      }
    }

    if (!(i & 1)) Ans[i / 2] = res;
  }
  For(i, 1, n / 2) cout << Ans[i] << ' ';
}