結果
問題 | No.1212 Second Path |
ユーザー |
![]() |
提出日時 | 2020-08-30 15:01:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 312 ms / 3,000 ms |
コード長 | 7,868 bytes |
コンパイル時間 | 5,253 ms |
コンパイル使用メモリ | 275,284 KB |
最終ジャッジ日時 | 2025-01-13 22:24:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <bits/extc++.h>#ifndef DUMP#define DUMP(...) void(0)#endifusing 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;elseres += 2 * mn;cout << res << '\n';}}