結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2021-02-27 20:46:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 214 ms / 2,000 ms |
コード長 | 7,490 bytes |
コンパイル時間 | 1,619 ms |
コンパイル使用メモリ | 147,840 KB |
最終ジャッジ日時 | 2025-01-19 08:05:49 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>using namespace std;using ll = long long;constexpr int INF = 1001001001;constexpr int mod = 1000000007;// constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}constexpr int MAXV = 100005;vector<vector<int>> g; // グラフ (隣接リスト表現)int64_t weight[MAXV]; // 頂点の重みvector<int> vs; // DFS で訪問した頂点を並べたものvector<int64_t> dat; // dat[i] := vs[i] の重み (葉方向,根方向)->(+.-)vector<int> sign; // sign[i] := dat[i] の正負int in[MAXV]; // in[v] := v が vs で最初に出現した場所int out[MAXV]; // out[v] := 根方向に向かう場所int depth[MAXV]; // 根からの深さvoid dfs(int from = 0, int par = -1, int d = 0){// 葉方向in[from] = vs.size();vs.emplace_back(from);dat.emplace_back(weight[from]);sign.emplace_back(1);depth[from] = d;for(int to : g[from]){if(to != par) dfs(to, from, d + 1);}// 根方向out[from] = vs.size();vs.emplace_back(from);dat.emplace_back(-weight[from]);sign.emplace_back(-1);}template<typename Monoid>struct SegmentTree{using F = function<Monoid(Monoid, Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid M1;SegmentTree(const F f, const Monoid& M1) : f(f), M1(M1) {}SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void resize(int n){sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x){seg[k + sz] = x;}void build(){for(int k = sz - 1; k > 0; --k){seg[k] = f(seg[k << 1], seg[k << 1 | 1]);}}void update(int k, const Monoid &x){k += sz;seg[k] = x;while(k >>= 1){seg[k] = f(seg[k << 1], seg[k << 1 | 1]);}}Monoid query(int a, int b){Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const{return seg[k + sz];}// (type = true) : find_last// (type = false) : find_firsttemplate<typename C>int find_subtree(int a, const C &check, Monoid &M, bool type){while(a < sz){Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]);if(check(nxt)) a = a << 1 | type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template<typename C>int find_first(int a, const C &check){Monoid L = M1;if(a <= 0){if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1){Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template<typename C>int find_last(int b, const C &check){Monoid R = M1;if(b >= sz){if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1){if(b & 1){Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};struct LCA{using G = vector<vector<int>>;const int ub_log;vector<int> depth;const G &g;vector<vector<int>> table;LCA(const G &g) : g(g), depth(g.size()), ub_log(32 - __builtin_clz(g.size())){table.assign(ub_log, vector<int>(g.size(), -1));}// 親番号と深さを dfs で求めるvoid dfs(int from, int par = -1, int dep = 0){table[0][from] = par;depth[from] = dep;for(auto &to : g[from]){if(to != par) dfs(to, from, dep + 1);}}void build(int root = 0){dfs(root);for(int k = 0; k + 1 < ub_log; ++k){for(int i = 0; i < table[k].size(); ++i){if(table[k][i] == -1) table[k + 1][i] = -1;// 頂点 i の 2^(k+1) 先にある頂点// = (頂点 i の 2^k 先の頂点) の 2^k 先にある頂点else table[k + 1][i] = table[k][table[k][i]];}}}// u と v の LCAint query(int u, int v){if(depth[u] > depth[v]) swap(u, v);// u と v の depth を同じにするv = get(v, depth[v] - depth[u]);if(u == v) return u;for(int i = ub_log - 1; i >= 0; --i){// 2^i 個辿った頂点が異なるときif(table[i][u] != table[i][v]){// LCA に到達していないので、(u, v) をその頂点に置き換える。u = table[i][u];v = table[i][v];}}return table[0][u];}// v の x 先の頂点を求めるint get(int v, int x){if(x <= 0) return v;for(int i = ub_log - 1; i >= 0; --i){if(x >> i & 1) v = table[i][v];}return v;}int length(int u, int v){int lca = query(u, v);return depth[u] + depth[v] - depth[lca] * 2;}void print(){for(int k = 0; k + 1 < ub_log; ++k){for(int i = 0; i < table[k].size(); ++i){cerr << table[k][i] << " ";}cerr << "\n";}}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;g.resize(N);for(int i = 1; i < N; ++i){int A, B;cin >> A >> B;g[A].emplace_back(B);g[B].emplace_back(A);}for(int i = 0; i < N; ++i) cin >> weight[i];dfs();int D = dat.size();auto op = [](ll a, ll b){return a + b;};SegmentTree<ll> seg(D, op, 0);for(int i = 0; i < D; ++i) seg.set(i, dat[i]);seg.build();LCA lca_table(g);lca_table.build();int M;cin >> M;ll ans = 0;for(int i = 0; i < M; ++i){int A, B, C;cin >> A >> B >> C;int lca = lca_table.query(A, B);ans += C * (seg.query(in[lca], in[A] + 1) + seg.query(in[lca], in[B] + 1) - dat[in[lca]]);}cout << ans << endl;return 0;}