結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2019-11-27 16:52:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 3,286 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 114,672 KB |
実行使用メモリ | 45,312 KB |
最終ジャッジ日時 | 2024-11-15 19:13:59 |
合計ジャッジ時間 | 3,450 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <limits>#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;template<class F>struct SparseTable {using T = typename F::T;vector<vector<T>> table;vector<int> u;SparseTable() = default;explicit SparseTable(const vector<T> &v) { build(v); }void build(const vector<T> &v) {int n = v.size(), m = 1;while ((1 << m) <= n) m++;table.assign(m, vector<T>(n));u.assign(n + 1, 0);for (int i = 2; i <= n; ++i) {u[i] = u[i >> 1] + 1;}for (int i = 0; i < n; ++i) {table[0][i] = v[i];}for (int i = 1; i < m; ++i) {int x = (1 << (i - 1));for (int j = 0; j < n; ++j) {table[i][j] = F::f(table[i - 1][j], table[i - 1][min(j + x, n - 1)]);}}}T query(int a, int b) {int l = b - a;return F::f(table[u[l]][a], table[u[l]][b - (1 << u[l])]);}};struct F {using T = pair<int, int>;static T f(T a, T b) { return min(a, b); }static T e() { return T{INF<int>, -1}; }};class Graph {SparseTable<F> table;void dfs_euler(int v, int p, int d, int &k) {id[v] = k;vs[k] = v;depth[k++] = d;for (auto &&u : G[v]) {if (u != p) {dfs_euler(u, v, d + 1, k);vs[k] = v;depth[k++] = d;}}}public:int n;vector<vector<int>> G;vector<int> vs, depth, id;explicit Graph(int n) : n(n), G(n), vs(2 * n - 1), depth(2 * n - 1), id(n), table() {};void add_edge(int a, int b) {G[a].emplace_back(b);G[b].emplace_back(a);}void eulertour(int root) {int k = 0;dfs_euler(root, -1, 0, k);}void buildLCA() {eulertour(0);vector<pair<int, int>> v(2 * n - 1);for (int i = 0; i < 2 * n - 1; ++i) {v[i] = make_pair(depth[i], i);}table.build(v);}int LCA(int u, int v) {if (id[u] > id[v]) swap(u, v);return vs[table.query(id[u], id[v] + 1).second];}};int main() {int n;cin >> n;Graph G(n);for (int i = 0; i < n - 1; ++i) {int a, b;scanf("%d %d", &a, &b);G.add_edge(a, b);}G.buildLCA();vector<int> dp(n);for (auto &&j : dp) scanf("%d", &j);auto val = dp;stack<int> s;vector<int> visited(n, 0);s.emplace(0);while(!s.empty()){int a = s.top(); s.pop();visited[a]++;for (auto &&i : G.G[a]) {if(!visited[i]) {s.emplace(i);dp[i] += dp[a];}}}int m;cin >> m;ll ans = 0;for (int i = 0; i < m; ++i) {int a, b, c;scanf("%d %d %d", &a, &b, &c);ans += c*(dp[a]+dp[b]-2*dp[G.LCA(a, b)]+val[G.LCA(a, b)]);}cout << ans << "\n";return 0;}