結果

問題 No.386 貪欲な領主
ユーザー tnakao0123
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/* -*- 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0