結果

問題 No.1215 都市消滅ビーム
コンテスト
ユーザー risujiroh
提出日時 2020-08-30 17:39:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,777 bytes
コンパイル時間 4,674 ms
コンパイル使用メモリ 269,040 KB
最終ジャッジ日時 2025-01-14 01:33:04
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

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);
  }
};

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 m) -> bool {
    int64_t cnt = pref.back() + pref_depth.back() < m;
    {
      int cur = -1;
      for (int l = 0, r = k; l < r; ++l) {
        cnt += pref[l] + (cur != -1 ? g.dep[cur] : -inf) < m;
        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) < m;
        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]) < m;
      }
    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