結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2019-03-19 17:26:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 6,276 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 188,832 KB |
実行使用メモリ | 14,720 KB |
最終ジャッジ日時 | 2024-09-14 01:00:19 |
合計ジャッジ時間 | 3,773 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include "bits/stdc++.h"using namespace std;struct RangeMinimumQuery{using type = int;static type id() { return INT_MAX; }static type op(const type &l, const type &r) { return std::min(l, r); }};struct RangeMaximumQuery{using type = int;static type id() { return -INT_MAX; }static type op(const type &l, const type &r) { return std::max(l, r); }};struct RangeSumQuery{using type = long long;static type id() { return 0; }static type op(const type &l, const type &r) { return l + r; }};template <typename M>class SegmentTree{using T = typename M::type;int n;std::vector<T> node;public:// v を基に初期化SegmentTree(const std::vector<T> &v){// n は v.size() 以上の最小の2冪n = 1;while (n < int(v.size()))n *= 2;node.resize(2 * n, M::id());// i の子 -> 2*i+1, 2*i+2 , 親 -> (i-1)/2for (int i = 0; i < int(v.size()); i++)node[i + n] = v[i];for (int i = n - 1; i >= 0; i--)node[i] = M::op(node[2 * i], node[2 * i + 1]);}// Monoid::id 初期化SegmentTree(int _n){// n は v.size() 以上の最小の2冪n = 1;while (n < _n)n *= 2;node.resize(2 * n, M::id());}// x 番目を val に更新void update(int x, T val){x += n;node[x] = val;while (x >>= 1){node[x] = M::op(node[2 * x], node[2 * x + 1]);}}// v[x] を M::op(v[x], val) に更新void operation(int x, T val){x += n;node[x] = M::op(node[x], val);while (x >>= 1){node[x] = M::op(node[2 * x], node[2 * x + 1]);}}// [a, b] の opT query(int l, int r){l += n;r += n;T retl = M::id(), retr = M::id();while (l < r){if (l & 1)retl = M::op(retl, node[l++]);if (r & 1)retr = M::op(node[--r], retr);l >>= 1;r >>= 1;}return M::op(retl, retr);}};// http://beet-aizu.hatenablog.com/entry/2017/12/12/235950struct HLDecomposition{int n, pos;vector<vector<int>> G;vector<int> vid, head, sub, hvy, par, dep, inv, type;HLDecomposition() {}HLDecomposition(int sz) : n(sz), pos(0), G(n),vid(n, -1), head(n), sub(n, 1), hvy(n, -1),par(n), dep(n), inv(n), type(n) {}void add_edge(int u, int v){G[u].push_back(v);G[v].push_back(u);}void build(vector<int> rs = vector<int>(1, 0)){int c = 0;for (int r : rs){dfs(r);bfs(r, c++);}}void dfs(int rt){using T = pair<int, int>;stack<T> st;par[rt] = -1;dep[rt] = 0;st.emplace(rt, 0);while (!st.empty()){int v = st.top().first;int &i = st.top().second;if (i < (int)G[v].size()){int u = G[v][i++];if (u == par[v])continue;par[u] = v;dep[u] = dep[v] + 1;st.emplace(u, 0);}else{st.pop();int res = 0;for (int u : G[v]){if (u == par[v])continue;sub[v] += sub[u];if (res < sub[u])res = sub[u], hvy[v] = u;}}}}void bfs(int r, int c){int &k = pos;queue<int> q({r});while (!q.empty()){int h = q.front();q.pop();for (int i = h; i != -1; i = hvy[i]){type[i] = c;vid[i] = k++;inv[vid[i]] = i;head[i] = h;for (int j : G[i])if (j != par[i] && j != hvy[i])q.push(j);}}}// for_each(vertex)// [l,r] <- attention!!void for_each(int u, int v, const function<void(int, int)> &f){while (1){if (vid[u] > vid[v])swap(u, v);f(max(vid[head[v]], vid[u]), vid[v]);if (head[u] != head[v])v = par[head[v]];elsebreak;}}// for_each(edge)// [l,r] <- attention!!void for_each_edge(int u, int v, const function<void(int, int)> &f){while (1){if (vid[u] > vid[v])swap(u, v);if (head[u] != head[v]){f(vid[head[v]], vid[v]);v = par[head[v]];}else{if (u != v)f(vid[u] + 1, vid[v]);break;}}}int lca(int u, int v){while (1){if (vid[u] > vid[v])swap(u, v);if (head[u] == head[v])return u;v = par[head[v]];}}int distance(int u, int v){return dep[u] + dep[v] - 2 * dep[lca(u, v)];}};int main(){cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;SegmentTree<RangeSumQuery> st(n);HLDecomposition hl(n);for (int i = 0; i < n - 1; i++){int a, b;cin >> a >> b;hl.add_edge(a, b);// hl.add_edge(b, a);}hl.build();for (int i = 0; i < n; i++){int index, u;cin >> u;index = hl.vid[i];st.update(index, u);}int m;cin >> m;long long ret = 0;while (m--){long long a, b, c;cin >> a >> b >> c;// a = hl.vid[a];// b = hl.vid[b];hl.for_each(a, b, [&](int l, int r) { ret += c * st.query(l, r + 1); });}cout << ret << endl;}