結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2024-09-03 14:47:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 4,949 bytes |
コンパイル時間 | 4,281 ms |
コンパイル使用メモリ | 265,468 KB |
実行使用メモリ | 35,188 KB |
最終ジャッジ日時 | 2024-09-03 14:47:38 |
合計ジャッジ時間 | 6,155 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>struct graph {struct edge {int from;int to;T cost;};vector<edge> edges;vector<vector<int>> g;int n;graph(int m) : n(m) {g.resize(n);}virtual int add(int from, int to, T cost) = 0;};template <typename T>struct tree : graph<T> {using graph<T>::edges;using graph<T>::g;using graph<T>::n;tree(int m) : graph<T>(m) {}int add(int from, int to, T cost = 1) {assert(0 <= from && from < n && 0 <= to && to < n);int id = (int)edges.size();assert(id < n - 1);g[from].push_back(id);g[to].push_back(id);edges.push_back({from, to, cost});return id;}};template <typename T>struct dfs_tree : tree<T> {using tree<T>::edges;using tree<T>::g;using tree<T>::n;vector<int> pv;vector<int> pe;vector<int> order;vector<int> pos;vector<int> end;vector<int> sz;vector<int> root;vector<int> depth;vector<T> dist;dfs_tree(int m) : tree<T>(m) {}void init() {pv = vector<int>(n, -1);pe = vector<int>(n, -1);order.clear();pos = vector<int>(n, -1);end = vector<int>(n, -1);sz = vector<int>(n, 0);root = vector<int>(n, -1);depth = vector<int>(n, -1);dist = vector<T>(n);}void clear() {pv.clear();pe.clear();order.clear();pos.clear();end.clear();sz.clear();root.clear();depth.clear();dist.clear();}void dfs(int v, bool clear_order = true) {if(pv.empty()) init();else if(clear_order) order.clear();dfs_from(v);}private:void _dfs(int v) {pos[v] = (int)order.size();order.push_back(v);sz[v] = 1;for(int id : g[v]) {if(id == pe[v]) continue;auto &e = edges[id];int to = e.from ^ e.to ^ v;depth[to] = depth[v] + 1;dist[to] = dist[v] + e.cost;pv[to] = v;pe[to] = id;root[to] = (root[v] != -1 ? root[v] : to);_dfs(to);sz[v] += sz[to];}end[v] = (int)order.size() - 1;}void dfs_from(int v) {depth[v] = 0;dist[v] = T{};root[v] = v;pv[v] = pe[v] = -1;_dfs(v);}};template <typename T>struct lca_tree : dfs_tree<T> {using dfs_tree<T>::edges;using dfs_tree<T>::g;using dfs_tree<T>::n;using dfs_tree<T>::pv;using dfs_tree<T>::pos;using dfs_tree<T>::end;using dfs_tree<T>::depth;int h;vector<vector<int>> pr;lca_tree(int m) : dfs_tree<T>(m) {}inline void build_lca() {assert(!pv.empty());int max_depth = 0;for(int i = 0; i < n; i++) max_depth = max(max_depth, depth[i]);h = 1;while((1 << h) <= max_depth) h++;pr.resize(n);for(int i = 0; i < n; i++) {pr[i].resize(h);pr[i][0] = pv[i];}for(int j = 1; j < h; j++) {for(int i = 0; i < n; i++) {pr[i][j] = (pr[i][j - 1] == -1 ? -1 : pr[pr[i][j - 1]][j - 1]);}}}inline bool anc(int x, int y) {return (pos[x] <= pos[y] && end[y] <= end[x]);}inline int go_up(int x, int up) {assert(!pr.empty());up = min(up, (1 << h) - 1);for(int j = h - 1; j >= 0; j--) {if(up & (1 << j)) {x = pr[x][j];if(x == -1) break;}}return x;}inline int lca(int x, int y) {assert(!pr.empty());if(anc(x, y)) return x;if(anc(y, x)) return y;for(int j = h - 1; j >= 0; j--) {if(pr[x][j] != -1 && !anc(pr[x][j], y)) {x = pr[x][j];}}return pr[x][0];}};int main() {int n; cin >> n;lca_tree<long long> G(n);for(int i = 1; i < n; i++) {int a, b; cin >> a >> b;G.add(a, b, 0);}vector<long long> W(n);for(int i = 0; i < n; i++) cin >> W[i];queue<int> que; que.push(0);vector<long long> dist(n, -1);dist[0] = W[0];while(!que.empty()) {int v = que.front(); que.pop();for(int id: G.g[v]) {auto &e = G.edges[id];int to = e.from ^ e.to ^ v;if(dist[to] != -1) continue;dist[to] = dist[v] + W[to];que.push(to);}}G.dfs(0);G.build_lca();long long ans = 0;int m; cin >> m;while(m--) {int a, b, c; cin >> a >> b >> c;int p = G.lca(a, b);ans += (dist[a] + dist[b] - 2 * dist[p] + W[p]) * c;}cout << ans << endl;}