結果

問題 No.1215 都市消滅ビーム
ユーザー risujirohrisujiroh
提出日時 2020-08-30 18:10:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,822 ms / 6,000 ms
コード長 9,127 bytes
コンパイル時間 4,542 ms
コンパイル使用メモリ 302,608 KB
実行使用メモリ 24,588 KB
最終ジャッジ日時 2024-04-27 12:52:32
合計ジャッジ時間 36,681 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 606 ms
11,392 KB
testcase_14 AC 574 ms
9,344 KB
testcase_15 AC 1,620 ms
17,160 KB
testcase_16 AC 365 ms
7,680 KB
testcase_17 AC 610 ms
14,972 KB
testcase_18 AC 657 ms
13,000 KB
testcase_19 AC 57 ms
6,940 KB
testcase_20 AC 1,222 ms
15,180 KB
testcase_21 AC 16 ms
6,940 KB
testcase_22 AC 910 ms
11,868 KB
testcase_23 AC 899 ms
14,352 KB
testcase_24 AC 745 ms
10,980 KB
testcase_25 AC 423 ms
10,048 KB
testcase_26 AC 938 ms
14,952 KB
testcase_27 AC 1,071 ms
18,372 KB
testcase_28 AC 587 ms
9,216 KB
testcase_29 AC 520 ms
9,344 KB
testcase_30 AC 302 ms
15,052 KB
testcase_31 AC 218 ms
7,296 KB
testcase_32 AC 79 ms
14,148 KB
testcase_33 AC 78 ms
12,108 KB
testcase_34 AC 2,708 ms
24,584 KB
testcase_35 AC 2,761 ms
24,584 KB
testcase_36 AC 3,310 ms
24,584 KB
testcase_37 AC 2,496 ms
24,464 KB
testcase_38 AC 3,822 ms
24,584 KB
testcase_39 AC 3,015 ms
24,588 KB
testcase_40 AC 2 ms
6,940 KB
testcase_41 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/extc++.h>

#ifndef DUMP
#define DUMP(...) void(0)
#endif

using namespace std;

struct graph {
  struct edge {
    static inline bool cost;
    int src, dst;
    int operator-(int v) const { return src ^ dst ^ v; }
  };
  int n, m;
  vector<edge> edges;
  vector<vector<pair<int, int>>> adj;
  graph(int _n = 0) : n(_n), m(0), adj(n) {}
  int add(const edge& e, bool directed = false) {
    edges.push_back(e);
    adj[e.src].emplace_back(m, e.dst);
    if (not directed) adj[e.dst].emplace_back(m, e.src);
    return m++;
  }
};

struct dfs_forest : graph {
  using T = decltype(edge::cost);
  vector<int> root, pv, pe, sz, dep, min_dep, last, ord, in, out;
  vector<T> dist;
  int trials;
  dfs_forest(int _n = 0) : graph(_n), dist(n), trials(0) {
    for (auto p : {&root, &pv, &pe, &sz, &dep, &min_dep, &last, &in, &out})
      p->assign(n, -1);
  }
  int add(const edge& e) { return graph::add(e); }
  void dfs(int v) {
    sz[v] = 1, min_dep[v] = dep[v], last[v] = trials;
    in[v] = size(ord), ord.push_back(v);
    for (auto [id, u] : adj[v]) {
      if (id == pe[v]) continue;
      if (last[u] == trials) {
        min_dep[v] = min(min_dep[v], dep[u]);
        continue;
      }
      root[u] = root[v], pv[u] = v, pe[u] = id, dep[u] = dep[v] + 1;
      dist[u] = dist[v] + edges[id].cost;
      dfs(u);
      sz[v] += sz[u], min_dep[v] = min(min_dep[v], min_dep[u]);
    }
    out[v] = size(ord);
  }
  void build(int r, bool clear_ord = true) {
    root[r] = r, pv[r] = pe[r] = -1, dep[r] = 0, dist[r] = T{};
    if (clear_ord) ord.clear();
    dfs(r);
    ++trials;
  }
  void build() {
    fill(begin(root), end(root), -1);
    for (int v = 0; v < n; ++v)
      if (root[v] == -1) build(v, v == 0);
  }
  int farther(int id) const {
    int u = edges[id].src, v = edges[id].dst;
    return dep[u] < dep[v] ? v : u;
  }
  bool spans(int id) const { return id == pe[farther(id)]; }
  bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; }
};

struct hld_forest : dfs_forest {
  vector<int> head;
  hld_forest(int _n = 0) : dfs_forest(_n), head(n) {}
  void dfs_hld(int v) {
    in[v] = size(ord), ord.push_back(v);
    sort(begin(adj[v]), end(adj[v]), [&](auto a, auto b) {
      int au = a.second, bu = b.second;
      return (a.first == pe[au]) * sz[au] > (b.first == pe[bu]) * sz[bu];
    });
    for (auto [id, u] : adj[v]) {
      if (id == pe[v] or not spans(id)) continue;
      head[u] = u == adj[v][0].second ? head[v] : u;
      dfs_hld(u);
    }
    out[v] = size(ord);
  }
  void build_hld(int r, bool clear_ord = true) {
    build(r, clear_ord);
    ord.erase(end(ord) - sz[r], end(ord));
    head[r] = r;
    dfs_hld(r);
  }
  void build_hld() {
    fill(begin(root), end(root), -1);
    for (int v = 0; v < n; ++v)
      if (root[v] == -1) build_hld(v, v == 0);
  }
  int lca(int u, int v) const {
    assert(root[u] == root[v]);
    while (true) {
      if (in[u] > in[v]) swap(u, v);
      if (head[u] == head[v]) return u;
      v = pv[head[v]];
    }
  }
  int d(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
  T distance(int u, int v) const {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
  }
  int la(int v, int d) const {
    assert(0 <= d), assert(d <= dep[v]);
    while (dep[head[v]] > d) v = pv[head[v]];
    return ord[in[head[v]] + (d - dep[head[v]])];
  }
  int next(int src, int dst) const {
    assert(root[src] == root[dst]), assert(src != dst);
    if (not anc(src, dst)) return pv[src];
    return la(dst, dep[src] + 1);
  }
  int next(int src, int dst, int k) const {
    assert(root[src] == root[dst]), assert(k >= 0);
    int v = lca(src, dst);
    if (k <= dep[src] - dep[v]) return la(src, dep[src] - k);
    k -= dep[src] - dep[v];
    assert(k <= dep[dst] - dep[v]);
    return la(dst, dep[v] + k);
  }
  vector<pair<int, int>> ascend(int src, int dst) const {
    vector<pair<int, int>> res;
    while (head[src] != head[dst]) {
      res.emplace_back(in[src], in[head[src]]);
      src = pv[head[src]];
    }
    if (src != dst) res.emplace_back(in[src], in[dst] + 1);
    return res;
  }
  vector<pair<int, int>> descend(int src, int dst) const {
    if (src == dst) return {};
    if (head[src] == head[dst]) return {{in[src] + 1, in[dst]}};
    auto res = descend(src, pv[head[dst]]);
    res.emplace_back(in[head[dst]], in[dst]);
    return res;
  }
  template <class F>
  void run(int src, int dst, F f, bool vertex = true) const {
    assert(root[src] == root[dst]);
    int v = lca(src, dst);
    for (auto [a, b] : ascend(src, v)) f(a + 1, b);
    if (vertex) f(in[v], in[v] + 1);
    for (auto [a, b] : descend(v, dst)) f(a, b + 1);
  }
};

template <class Key, class T, class Comp = less<Key>>
using tree_map =
    __gnu_pbds::tree<Key, T, Comp, __gnu_pbds::rb_tree_tag,
                     __gnu_pbds::tree_order_statistics_node_update>;
template <class Key, class Comp = less<Key>>
using tree_set = tree_map<Key, __gnu_pbds::null_type, Comp>;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  vector<int> pos(k), val(k);
  for (auto&& e : pos) cin >> e, --e;
  for (auto&& e : val) cin >> e;
  hld_forest g(n);
  for (int _ = n - 1; _--;) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g.add({u, v});
  }
  g.build_hld();

  vector<int64_t> pref(k + 1);
  for (int i = 0; i < k; ++i) pref[i + 1] = pref[i] + val[i];
  vector<int64_t> suff(k + 1);
  for (int i = k; i--;) suff[i] = val[i] + suff[i + 1];

  assert(k >= 2);
  int lca = g.lca(pos[0], pos.back());
  vector<int> pref_lca(k + 1, lca), pref_depth(k + 1, g.dep[lca]);
  for (int i = 0; i < k; ++i) {
    pref_lca[i + 1] = g.lca(pref_lca[i], pos[i]);
    pref_depth[i + 1] = g.dep[pref_lca[i + 1]];
  }
  vector<int> suff_lca(k + 1, lca), suff_depth(k + 1, g.dep[lca]);
  for (int i = k; i--;) {
    suff_lca[i] = g.lca(pos[i], suff_lca[i + 1]);
    suff_depth[i] = g.dep[suff_lca[i]];
  }
  DUMP(pref_depth);
  DUMP(suff_depth);

  constexpr int64_t inf = 1e15;

  auto check = [&](auto mid) -> bool {
    int64_t cnt = pref.back() + pref_depth.back() < mid;
    {
      int cur = -1;
      for (int l = 0, r = k; l < r; ++l) {
        cnt += pref[l] + (cur != -1 ? g.dep[cur] : -inf) < mid;
        cur = cur != -1 ? g.lca(cur, pos[l]) : pos[l];
      }
    }
    {
      int cur = -1;
      for (int l = 0, r = k; l < r; --r) {
        cnt += r < k and suff[r] + (cur != -1 ? g.dep[cur] : -inf) < mid;
        cur = cur != -1 ? g.lca(cur, pos[r - 1]) : pos[r - 1];
      }
    }

    for (int r = 1; r < k; ++r)
      for (int l = 1; l < r; ++l) {
        // cnt += pref[l] + suff[r] + min(pref_depth[l], suff_depth[r]) < mid;
      }

    int m = 0;
    while (suff_depth[m] < pref_depth[m]) ++m;
    // 0 < l < r <= m, pref[l] + suff[r] + suff_depth[r] < mid
    {
      tree_set<pair<int64_t, int>> se;
      int t = 0;
      for (int l = m - 1; l > 0; --l) {
        if (l + 1 < k) se.insert({suff[l + 1] + suff_depth[l + 1], t++});
        cnt += se.order_of_key({mid - pref[l], 0});
      }
    }
    // m <= l < r < k, pref[l] + suff[r] + pref_depth[l] < mid
    {
      tree_set<pair<int64_t, int>> se;
      int t = 0;
      for (int r = m + 1; r < k; ++r) {
        if (r - 1 > 0) se.insert({pref[r - 1] + pref_depth[r - 1], t++});
        cnt += se.order_of_key({mid - suff[r], 0});
      }
    }
    // 0 < l < m < r < k,
    // pref[l] + suff[r] + min(pref_depth[l], suff_depth[r]) < mid
    if (2 <= m and m <= k - 2) {
      vector<int> ord_l(m - 1), ord_r(k - m - 1);
      iota(begin(ord_l), end(ord_l), 1);
      iota(begin(ord_r), end(ord_r), m + 1);
      sort(begin(ord_l), end(ord_l),
           [&](int i, int j) { return pref_depth[i] > pref_depth[j]; });
      sort(begin(ord_r), end(ord_r),
           [&](int i, int j) { return suff_depth[i] > suff_depth[j]; });
      // pref_depth[l] < suff_depth[r]
      {
        tree_set<pair<int64_t, int>> se;
        int t = 0;
        auto it = begin(ord_r);
        for (int l : ord_l) {
          while (it != end(ord_r) and suff_depth[*it] > pref_depth[l]) {
            se.insert({suff[*it], t++});
            ++it;
          }
          cnt += se.order_of_key({mid - pref[l] - pref_depth[l], 0});
        }
      }
      // pref_depth[l] >= suff_depth[r]
      {
        tree_set<pair<int64_t, int>> se;
        int t = 0;
        auto it = begin(ord_l);
        for (int r : ord_r) {
          while (it != end(ord_l) and pref_depth[*it] >= suff_depth[r]) {
            se.insert({pref[*it], t++});
            ++it;
          }
          cnt += se.order_of_key({mid - suff[r] - suff_depth[r], 0});
        }
      }
    }
    return cnt <= int64_t(k) * (k + 1) / 4;
  };

  int64_t ok = -inf, ng = inf;
  while (ng - ok > 1) {
    auto mid = (ok + ng) / 2;
    (check(mid) ? ok : ng) = mid;
  }
  cout << ok << '\n';
}
0