結果

問題 No.1212 Second Path
ユーザー risujirohrisujiroh
提出日時 2020-08-30 15:01:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 242 ms / 3,000 ms
コード長 7,868 bytes
コンパイル時間 5,463 ms
コンパイル使用メモリ 288,100 KB
実行使用メモリ 32,180 KB
最終ジャッジ日時 2024-11-15 08:28:23
合計ジャッジ時間 17,291 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 145 ms
32,180 KB
testcase_01 AC 210 ms
31,328 KB
testcase_02 AC 208 ms
29,872 KB
testcase_03 AC 212 ms
30,256 KB
testcase_04 AC 220 ms
27,752 KB
testcase_05 AC 199 ms
27,824 KB
testcase_06 AC 225 ms
21,356 KB
testcase_07 AC 233 ms
21,912 KB
testcase_08 AC 237 ms
22,004 KB
testcase_09 AC 237 ms
22,028 KB
testcase_10 AC 238 ms
21,920 KB
testcase_11 AC 232 ms
22,028 KB
testcase_12 AC 232 ms
21,920 KB
testcase_13 AC 240 ms
21,848 KB
testcase_14 AC 227 ms
22,036 KB
testcase_15 AC 242 ms
22,044 KB
testcase_16 AC 237 ms
21,792 KB
testcase_17 AC 142 ms
32,128 KB
testcase_18 AC 44 ms
6,820 KB
testcase_19 AC 43 ms
6,820 KB
testcase_20 AC 44 ms
6,816 KB
testcase_21 AC 39 ms
6,820 KB
testcase_22 AC 43 ms
6,816 KB
testcase_23 AC 25 ms
6,820 KB
testcase_24 AC 30 ms
6,820 KB
testcase_25 AC 28 ms
6,820 KB
testcase_26 AC 30 ms
6,816 KB
testcase_27 AC 29 ms
6,816 KB
testcase_28 AC 29 ms
6,816 KB
testcase_29 AC 188 ms
32,140 KB
testcase_30 AC 184 ms
32,112 KB
testcase_31 AC 182 ms
32,156 KB
testcase_32 AC 192 ms
17,088 KB
testcase_33 AC 166 ms
13,988 KB
testcase_34 AC 222 ms
20,772 KB
testcase_35 AC 90 ms
6,816 KB
testcase_36 AC 191 ms
17,724 KB
testcase_37 AC 191 ms
16,500 KB
testcase_38 AC 193 ms
17,080 KB
testcase_39 AC 141 ms
10,984 KB
testcase_40 AC 62 ms
6,816 KB
testcase_41 AC 192 ms
17,224 KB
testcase_42 AC 2 ms
6,816 KB
testcase_43 AC 2 ms
6,820 KB
testcase_44 AC 2 ms
6,816 KB
testcase_45 AC 227 ms
21,360 KB
testcase_46 AC 220 ms
21,316 KB
testcase_47 AC 222 ms
21,272 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/extc++.h>

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

using namespace std;

struct graph {
  struct edge {
    int src, dst;
    int64_t cost;
    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);
  }
};

constexpr int inf = 0x3f3f3f3f;

template <class T>
struct segtree {
  int n;
  vector<T> t;
  segtree(int _n = 0) : n(_n), t(2 * n) {}
  T& operator[](int i) { return t[n + i]; }
  void build() {
    for (int i = n; i-- > 1;) t[i] = t[2 * i] * t[2 * i + 1];
  }
  T fold(int l, int r) const {
    T a{}, b{};
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) a = a * t[l++];
      if (r & 1) b = t[--r] * b;
    }
    return a * b;
  }
  void set(int i, const T& a) {
    t[i += n] = a;
    while (i >>= 1) t[i] = t[2 * i] * t[2 * i + 1];
  }
};

struct node {
  int v;
  node(int _v = inf) : v(_v) {}
  operator int() const { return v; }
  friend node operator*(const node& a, const node& b) {
    return b.v < a.v ? b : a;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  hld_forest g(n);
  for (int _ = n - 1; _--;) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g.add({u, v, w});
  }
  g.build_hld();

  segtree<node> seg(n);
  vector<segtree<node>> ch(n);
  vector<int> sz(n);
  for (int v = 0; v < n; ++v) {
    sz[v] = size(g.adj[v]) - (v >= 1);
    ch[v] = sz[v];
    for (int i = 0; i < sz[v]; ++i) {
      auto [id, u] = g.adj[v][i];
      ch[v][i] = g.edges[id].cost;
    }
    ch[v].build();
    for (int i = 0; i < sz[v]; ++i) {
      auto [id, u] = g.adj[v][i];
      seg[g.in[u]] = min(ch[v].fold(0, i), ch[v].fold(i + 1, sz[v]));
    }
  }
  seg.build();

  auto fold = [&](int u, int v) {
    int res = inf;
    g.run(
        u, v,
        [&](int l, int r) {
          if (l > r) swap(l, r);
          res = min<int>(res, seg.fold(l, r));
        },
        false);
    return res;
  };

  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    if (g.in[u] > g.in[v]) swap(u, v);
    int a = g.lca(u, v);
    int64_t res = g.distance(u, v);
    int mn = inf;
    if (u == a) {
      mn = min(mn, fold(u, v));
      mn = min<int>(mn, ch[v].fold(0, sz[v]));
    } else {
      int au = g.next(a, u);
      int av = g.next(a, v);
      mn = min(mn, fold(u, au));
      mn = min(mn, fold(v, av));
      mn = min<int>(mn, ch[u].fold(0, sz[u]));
      mn = min<int>(mn, ch[v].fold(0, sz[v]));
      assert(g.in[au] < g.in[av]);
      int x = partition_point(
                  begin(g.adj[a]), begin(g.adj[a]) + sz[a],
                  [&](auto idu) { return g.in[idu.second] < g.in[au]; }) -
              begin(g.adj[a]);
      int y = partition_point(
                  begin(g.adj[a]), begin(g.adj[a]) + sz[a],
                  [&](auto idu) { return g.in[idu.second] < g.in[av]; }) -
              begin(g.adj[a]);
      mn = min<int>(mn, ch[a].fold(0, x));
      mn = min<int>(mn, ch[a].fold(x + 1, y));
      mn = min<int>(mn, ch[a].fold(y + 1, sz[a]));
    }
    if (a) mn = min<int>(mn, g.edges[g.pe[a]].cost);
    if (mn == inf)
      res = -1;
    else
      res += 2 * mn;
    cout << res << '\n';
  }
}
0