結果
| 問題 | No.1094 木登り / Climbing tree |
| ユーザー |
 tkmst201
|
| 提出日時 | 2021-03-11 12:30:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 992 ms / 2,000 ms |
| コード長 | 5,352 bytes |
| 記録 | |
| コンパイル時間 | 1,695 ms |
| コンパイル使用メモリ | 85,276 KB |
| 最終ジャッジ日時 | 2025-01-19 13:30:39 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:207:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
207 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
main.cpp:212:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
212 | scanf("%d %d %d", &A[i], &B[i], &C[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:229:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
229 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
main.cpp:232:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
232 | scanf("%d %d", &s, &t);
| ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include <vector>
#include <cassert>
#include <stack>
#include <utility>
template<bool EDGE = true>
struct EulerTour {
using size_type = std::size_t;
using Graph = std::vector<std::vector<int>>;
private:
int n, root;
std::vector<int> in_, out_, par_, g_idx;
public:
EulerTour(const Graph & g, int root = 0)
: n(g.size()), root(root), in_(size(), -1), out_(size(), -1), par_(n, -1), g_idx(n << 1, -1) {
std::stack<std::pair<int, int>> stk;
int num = 0;
in_[root] = num++;
stk.emplace(root, 0);
while (!stk.empty()) {
auto [u, i] = stk.top();
stk.pop();
if (i < g[u].size()) {
const int v = g[u][i];
stk.emplace(u, i + 1);
if (v == par_[u]) g_idx[u << 1 | 1] = i;
else {
in_[v] = num++;
par_[v] = u;
g_idx[v << 1] = i;
stk.emplace(v, 0);
}
}
else {
out_[u] = num;
if (EDGE) ++num;
}
}
}
size_type size() const noexcept {
return EDGE ? n << 1 : n;
}
int par(int k) const noexcept {
assert(0 <= k && k < n);
return par_[k];
}
int in(int k) const noexcept {
assert(0 <= k && k < n);
return in_[k];
}
int out(int k) const noexcept {
assert(0 <= k && k < n);
return out_[k];
}
std::pair<int, int> par_from(int k) const noexcept {
assert(0 <= k && k < n);
return {par_[k], g_idx[k << 1]};
}
int par_to(int k) const noexcept {
assert(0 <= k && k < n);
return g_idx[k << 1 | 1];
}
};
#include <vector>
#include <cassert>
#include <functional>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree.hpp
*/
template<typename T>
struct BinaryIndexedTree {
using value_type = T;
using const_reference = const value_type &;
using F = std::function<value_type (const_reference, const_reference)>;
using size_type = std::size_t;
private:
size_type n;
value_type id_elem;
F f;
std::vector<value_type> node;
public:
BinaryIndexedTree(size_type n, const_reference id_elem, const F & f)
: n(n), id_elem(id_elem), f(f), node(n + 1, id_elem) {}
size_type size() const noexcept {
return n;
}
void add(size_type i, const_reference x) noexcept {
assert(i < size());
++i;
for (; i <= size(); i += i & -i) node[i] = f(node[i], x);
}
value_type sum(size_type i) const noexcept {
assert(i <= size());
value_type res = id_elem;
for (; i > 0; i -= i & -i) res = f(node[i], res);
return res;
}
size_type lower_bound(const_reference x) const noexcept {
size_type res = 0;
size_type s = id_elem, w = 1;
while (w < size()) w <<= 1;
for (; w > 0; w >>= 1) {
if (res + w <= size()) {
value_type cur = f(s, node[res + w]);
if (cur < x) {
res += w;
s = cur;
}
}
}
return res;
}
};
/**
* @brief https://tkmst201.github.io/Library/GraphTheory/LowestCommonAncestor.hpp
*/
struct LowestCommonAncestor {
using size_type = std::size_t;
using Graph = std::vector<std::vector<int>>;
private:
int n, logn;
std::vector<std::vector<int>> par;
std::vector<int> depth_;
public:
LowestCommonAncestor(const Graph & g, int root = 0) : n(g.size()) {
assert(0 <= root && root < size());
logn = 1;
while ((1 << logn) + 1 <= size()) ++logn;
par.assign(logn, std::vector<int>(size()));
depth_.assign(size(), 0);
std::stack<std::pair<int, int>> stk;
par[0][root] = root;
stk.emplace(root, root);
while (!stk.empty()) {
auto [u, p] = stk.top();
stk.pop();
for (int v : g[u]) {
if (v == p) continue;
assert(0 <= v && v < size());
par[0][v] = u;
depth_[v] = depth_[u] + 1;
stk.emplace(v, u);
}
}
for (int i = 1; i < logn; ++i) {
for (int j = 0; j < size(); ++j) par[i][j] = par[i - 1][par[i - 1][j]];
}
}
size_type size() const noexcept {
return n;
}
int find(int a, int b) const noexcept {
assert(0 <= a && a < size());
assert(0 <= b && b < size());
assert(par[0][a] != size());
assert(par[0][b] != size());
if (depth_[a] < depth_[b]) std::swap(a, b);
a = parent(a, depth_[a] - depth_[b]);
if (a == b) return a;
for (int i = logn - 1; i >= 0; --i) {
if (par[i][a] != par[i][b]) a = par[i][a], b = par[i][b];
}
return par[0][a];
}
int parent(int u, int k = 1) const noexcept {
assert(0 <= u && u < size());
assert(k <= depth_[u]);
assert(par[0][u] != size());
for (int i = 0; i < logn; ++i) if (k >> i & 1) u = par[i][u];
return u;
}
int depth(int u) const noexcept {
assert(0 <= u && u < size());
assert(par[0][u] != size());
return depth_[u];
}
};
#include <cstdio>
#include <utility>
int main() {
int N;
scanf("%d", &N);
EulerTour<true>::Graph g(N);
std::vector<int> A(N - 1), B(N - 1), C(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d %d %d", &A[i], &B[i], &C[i]);
--A[i]; --B[i];
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
EulerTour<true> et(g);
using ll = long long;
BinaryIndexedTree<ll> bit(et.size(), 0, [](auto x, auto y) { return x + y; });
for (int i = 0; i < N - 1; ++i) {
if (et.par(A[i]) != B[i]) std::swap(A[i], B[i]);
bit.add(et.in(A[i]), C[i]);
bit.add(et.out(A[i]), -C[i]);
}
LowestCommonAncestor lca(g);
int Q;
scanf("%d", &Q);
while (Q--) {
int s, t;
scanf("%d %d", &s, &t);
--s; --t;
const int l = lca.find(s, t);
auto func = [&](int a) {
return bit.sum(et.in(a) + 1) - bit.sum(et.in(l) + 1);
};
printf("%lld\n", func(s) + func(t));
}
}