結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-14 19:35:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 318 ms / 2,000 ms |
コード長 | 2,081 bytes |
コンパイル時間 | 807 ms |
コンパイル使用メモリ | 93,808 KB |
実行使用メモリ | 17,664 KB |
最終ジャッジ日時 | 2024-10-14 17:13:29 |
合計ジャッジ時間 | 3,756 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
/* -*- coding: utf-8 -*-** 386.cc: No.386 貪欲な領主 - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 100000;const int BN = 17;/* typedef */typedef long long ll;typedef vector<int> vi;struct Stat {int i, p, d;Stat() {}Stat(int _i, int _p, int _d): i(_i), p(_p), d(_d) {}};/* global variables */vi nbrs[MAX_N];int us[MAX_N], ds[MAX_N], prts[MAX_N][BN];ll usums[MAX_N];/* subroutines *//* main */int main() {int n;cin >> n;for (int i = 0; i < n - 1; i++) {int ai, bi;cin >> ai >> bi;nbrs[ai].push_back(bi);nbrs[bi].push_back(ai);}for (int i = 0; i < n; i++) cin >> us[i];ds[0] = 0;prts[0][0] = -1;usums[0] = us[0];queue<Stat> q;q.push(Stat(0, -1, 0));while (! q.empty()) {Stat u = q.front(); q.pop();vi &nbru = nbrs[u.i];int vd = u.d + 1;for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {int &vi = *vit;if (vi != u.p) {ds[vi] = vd;prts[vi][0] = u.i;usums[vi] = usums[u.i] + us[vi];q.push(Stat(vi, u.i, vd));}}}for (int i = 1; i < BN; i++)for (int j = 0; j < n; j++) {int &p = prts[j][i - 1];prts[j][i] = (p < 0) ? -1 : prts[p][i - 1];}int m;cin >> m;ll sum = 0;while (m--) {int ai, bi, ci;cin >> ai >> bi >> ci;int u = ai, v = bi;if (ds[u] > ds[v]) swap(u, v);for (int i = BN - 1; i >= 0; i--)if (((ds[v] - ds[u]) >> i) & 1) v = prts[v][i];if (u != v) {for (int i = BN - 1; i >= 0; i--)if (prts[u][i] != prts[v][i])u = prts[u][i], v = prts[v][i];u = prts[u][0];}sum += (usums[ai] + usums[bi] - usums[u] * 2 + us[u]) * ci;}printf("%lld\n", sum);return 0;}