結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2023-02-14 12:11:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 273 ms / 2,000 ms |
コード長 | 2,186 bytes |
コンパイル時間 | 3,890 ms |
コンパイル使用メモリ | 253,896 KB |
最終ジャッジ日時 | 2025-02-10 15:17:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define rep(i, n) for (int i = 0; i < (int)(n); i++)using namespace atcoder;using ll = long long;const ll MOD1 = 1000000007LL;const ll MOD2 = 998244353LL;using namespace std;const vector<pair<int, int>> dpos4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};// const vector<pair<int, int>> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}// aよりもbが小さいならばaをbで更新する// (更新されたならばtrueを返す)template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}int main() {int N;cin >> N;vector<vector<int>> edges(N);rep(i, N - 1){int a, b; cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}vector<ll> U(N);rep(i, N) cin >> U[i];vector<int> depth(N, 0);vector<ll> money(N, 0);vector<vector<int>> parent(20, vector<int>(N, 0));money[0] = U[0];auto dfs = [&](auto self, int fr, int prev=-1) -> void {for(auto to: edges[fr]){if(to == prev) continue;depth[to] = depth[fr] + 1;money[to] = money[fr] + U[to];parent[0][to] = fr;self(self, to, fr);}};dfs(dfs, 0);for(int i = 1; i < 20; i++){rep(j, N){parent[i][j] = parent[i - 1][parent[i - 1][j]];}}auto get_lca = [&](int a, int b) {if(depth[a] < depth[b]) swap(a, b);int d = depth[a] - depth[b];rep(i, 20){if((d >> i) % 2 == 1) a = parent[i][a];}if(a == b) return a;for(int i = 19; i >= 0; i--){if(parent[i][a] == parent[i][b]) continue;a = parent[i][a];b = parent[i][b];}return parent[0][a];};auto calc = [&](int a, int b){int p = get_lca(a, b);ll ans = money[a] + money[b] - 2 * money[p] + U[p];return ans;};int M;cin >> M;ll ans = 0;rep(i, M){int a, b, c;cin >> a >> b >> c;ans += calc(a, b) * c;}cout << ans << endl;return 0;}