[AGC007E] Shik and Travel 题解

· · 题解

考虑二分答案，问题转化为判定答案是否 \le v。每条边恰好经过两次的约束等价于我们必须以深度优先遍历的顺序经过所有叶子，这启示我们使用树形 dp。

设 f_{x,a,b} 表示只考虑以 x 为根的子树，并且从 x 到第一个儿子的距离为 a，从最后一个儿子回到 x 的距离为 b 时是否存在可行方案。

有转移方程 f_{l_x,a,b}\land f_{r_x,c,d}\land b+w(x,l_x)+w(x,r_x)+c\le v\implies f_{x,a+w(x,l_x),d+w(x,r_x)}\land f_{x,c+w(x,r_x),b+w(x,l_x)}。

直接做这个东西显然是会爆炸的，考虑优化。

注意到如果 f_{x,a,b} 成立，那么对所有 c\ge a,d\ge b，f_{x,c,d} 都是没用的了。把有效的状态留下后对 a 升序排序，则 b 相应的单调递减。

设点 x 处的有效状态数为 F_x。由于 x 上的一个状态 f_{x,a,b} 里的 a 必然来自于 l_x 与 r_x，且 b 必然来自于相应的 r_x 与 l_x，因为有效状态的 a 和 b 不能重复（否则我们必然可以删掉另一维更大的状态），所以有不等式 F_x\le 2\min(F_{l_x},F_{r_x})，由启发式合并可以知道总状态数是 \mathcal{O}(n\log n)，因此我们只需要在较优的时间复杂度内不重不漏的进行转移。

关于 \sum F=\mathcal{O}(n\log n) 的一个证明：

由 F_x\le 2\min(F_{l_x},F_{r_x})\le F_{l_x}+F_{r_x} 可以得到 F_x\le\mathrm{size}_x，因此有 \sum F\le 2\sum\min(F_{l_x},F_{r_x})\le 2\sum\min(\mathrm{size}_{l_x},\mathrm{size}_{r_x})，而最后这个式子就是经典的启发式合并，因此 \sum F=\mathcal{O}(n\log n)。

跑两遍双指针可以得到所有合法状态，合并后去除没用的状态即可。时间复杂度 \mathcal{O}(n\log n\log v)。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;
using Pll = pair<LL, LL>;

const int kN = (1 << 17) + 1;

struct E {
  int y, w;
};
int n;
vector<E> e[kN];
vector<Pll> f[kN];

void D(int x, LL v) {
  if (e[x].empty()) {
    f[x].emplace_back(0, 0);
    return;
  }
  D(e[x][0].y, v), D(e[x][1].y, v);
  vector<Pll> _f[2];
  for (int o = 0; o < 2; ++o) {
    int l = e[x][o].y, r = e[x][!o].y;
    int lw = e[x][o].w, rw = e[x][!o].w;
    for (int i = 0, j = 0; i < f[l].size(); ++i) {
      for (; j + 1 < f[r].size() && f[l][i].second + f[r][j + 1].first + lw + rw <= v; ++j) {
      }
      if (j < f[r].size() && f[l][i].second + f[r][j].first + lw + rw <= v) {
        _f[o].emplace_back(f[l][i].first + lw, f[r][j].second + rw);
      }
    }
  }
  vector<Pll> rf(_f[0].size() + _f[1].size());
  merge(_f[0].begin(), _f[0].end(), _f[1].begin(), _f[1].end(), rf.begin());
  for (Pll i : rf) {
    if (f[x].empty() || f[x].back().first < i.first && f[x].back().second > i.second) {
      f[x].push_back(i);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 2, y, w; i <= n; ++i) {
    cin >> y >> w;
    e[y].push_back({i, w});
  }
  LL l = 0, r = 1e12;
  while (l < r) {
    LL m = l + r >> 1;
    for (int i = 1; i <= n; ++i) {
      f[i].clear();
    }
    D(1, m);
    if (f[1].empty()) {
      l = m + 1;
    } else {
      r = m;
    }
  }
  cout << l;
  return 0;
}