結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-02 06:58:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 2,064 bytes |
コンパイル時間 | 1,953 ms |
コンパイル使用メモリ | 181,356 KB |
実行使用メモリ | 20,600 KB |
最終ジャッジ日時 | 2024-10-12 19:43:12 |
合計ジャッジ時間 | 3,724 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)typedef long long ll;int N;vector<int> E[101010];int U[101010];//-----------------------------------------------------------------int sum[101010];void bfs() {queue<int> que;sum[0] = U[0];que.push(0);while (!que.empty()) {int i = que.front(); que.pop();for (int j : E[i]) if (sum[j] == 0) {sum[j] = sum[i] + U[j];que.push(j);}}}//-----------------------------------------------------------------class LCA{public:int NV;int logNV;vector<int> D;vector<long long> L;vector<vector<int> > P;LCA(int N){NV = N;logNV = 0;while (NV > (1LL << logNV)) logNV++;D = vector<int>(NV);L = vector<long long>(NV);P = vector<vector<int> >(logNV, vector<int>(NV));}void init(){dfs(0, -1, 0, 0);build();}void dfs(int v, int par, int d, long long l){D[v] = d;P[0][v] = par;L[v] = l;for (int i = 0; i < (int)E[v].size(); i++) {int w = E[v][i];int lc = 1;if (w == par) continue;dfs(w, v, d + 1, lc + l);}}void build() {for (int k = 0; k + 1 < logNV; k++) {for (int v = 0; v < NV; v++) {if (P[k][v] < 0) P[k + 1][v] = -1;else P[k + 1][v] = P[k][P[k][v]];}}}int query(int u, int v) {if (D[u] > D[v]) swap(u, v);for (int k = 0; k < logNV; k++) {if ((D[v] - D[u]) >> k & 1)v = P[k][v];}if (u == v) return u;for (int k = logNV - 1; k >= 0; k--) {if (P[k][u] != P[k][v]) {u = P[k][u];v = P[k][v];}}return P[0][u];}};//-----------------------------------------------------------------int main() {scanf("%d", &N);rep(i, 0, N - 1) {int a, b; scanf("%d %d", &a, &b);E[a].push_back(b);E[b].push_back(a);}rep(i, 0, N) scanf("%d", &U[i]);bfs();LCA lca(N);lca.init();int M; scanf("%d", &M);ll ans = 0;rep(i, 0, M) {int a, b, c; scanf("%d %d %d", &a, &b, &c);int p = lca.query(a, b);ans += (sum[a] + sum[b] - sum[p] * 2 + U[p]) * c;}printf("%lld\n", ans);}