結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2019-08-21 01:24:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 299 ms / 2,000 ms |
コード長 | 2,212 bytes |
コンパイル時間 | 940 ms |
コンパイル使用メモリ | 82,896 KB |
実行使用メモリ | 23,608 KB |
最終ジャッジ日時 | 2024-10-06 16:17:19 |
合計ジャッジ時間 | 3,640 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>using namespace std;using UnWeightedGraph = vector<vector<int>>;struct LowestCommonAncestor {const UnWeightedGraph &g;int root;vector<vector<int>> parent; // parent[k][v] := 2^k-th parent of vvector<int> depth;LowestCommonAncestor(const UnWeightedGraph &g, int r = 0) : \g(g), root(r), depth(g.size()) { }void build() {int V = g.size();int h = 1; while ((1 << h) < V) ++h; // 32 - __builtin_clz(V)parent.assign(h, vector<int>(V, -1));dfs(root, -1, 0);for (int k = 0; k + 1 < h; ++k) for (int v = 0; v < V; ++v) {if (parent[k][v] != -1) parent[k + 1][v] = parent[k][parent[k][v]];}}void dfs(int u, int p, int d) {parent[0][u] = p;depth[u] = d;for (auto v: g[u]) if (v != p) dfs(v, u, d + 1);}int get(int u, int v) {if (depth[u] > depth[v]) swap(u, v);for (int k = 0; k < parent.size(); ++k) {if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];}if (u == v) return u;for (int k = parent.size() - 1; k >= 0; --k) {if (parent[k][u] != parent[k][v]) {u = parent[k][u]; v = parent[k][v];}}return parent[0][u];}int dist(int u, int v) { return depth[u] + depth[v] - depth[get(u, v)] * 2; }};vector<long long> cost, acc;void rec(const UnWeightedGraph &g, int u, int p, int c) {acc[u] = c + cost[u];for (auto v: g[u]) if (v != p) {rec(g, v, u, acc[u]);}}int main() {int N; cin >> N;UnWeightedGraph g(N);for (int i = 0; i < N - 1; i++) {int a, b; cin >> a >> b;g[a].emplace_back(b);g[b].emplace_back(a);}LowestCommonAncestor lca(g);lca.build();cost.resize(N); acc.resize(N);for (auto &ci: cost) cin >> ci;rec(g, 0, -1, 0);long long res = 0;int Q; cin >> Q;while (Q--) {int a, b, c; cin >> a >> b >> c;int p = lca.get(a, b);res += (acc[a] + acc[b] - acc[p] * 2 + cost[p]) * c;}cout << res << endl;return 0;}