結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2016-07-07 11:24:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 1,869 bytes |
コンパイル時間 | 619 ms |
コンパイル使用メモリ | 64,844 KB |
実行使用メモリ | 24,244 KB |
最終ジャッジ日時 | 2024-10-12 23:00:51 |
合計ジャッジ時間 | 3,821 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <iostream>#include <vector>using namespace std;#define MAXN (100000+1)#define MAXM (200000+1)int N, M;vector<int> tree[MAXN];int cost[MAXN];int cost_sum[MAXN];int depth[MAXN];int log_n;vector<vector<int> > par;void dfs(int v, int p, int c, int d){par[0][v] = p;depth[v] = d;cost_sum[v] = cost[v] + c;for (int i = 0; i < tree[v].size(); i++) {if (tree[v][i] != p) {dfs(tree[v][i], v, cost_sum[v], d+1);}}}void init(){while (N > (1 << log_n)) log_n++;par = vector<vector<int> >(log_n, vector<int>(N));dfs(0, -1, 0, 0);for (int k = 0; k < log_n-1; k++) {for(int v = 0; v < N; v++) {if (par[k][v] < 0) {par[k+1][v] = -1;}else {par[k+1][v] = par[k][par[k][v]];}}}}int solve(int u, int v){if (depth[u] > depth[v]) {swap(u, v);}for (int k = 0; k < log_n; k++) {if((depth[v] - depth[u]) >> k & 1)v = par[k][v];}if(u==v)return u;for (int k = log_n-1; k >= 0; k--) {if (par[k][u] != par[k][v]) {u = par[k][u];v = par[k][v];}}return par[0][u];}int main(){cin.tie(0);ios::sync_with_stdio(false);cin >> N;for (int n = 0; n < (N-1); n++) {int a, b;cin >> a;cin >> b;tree[a].push_back(b);tree[b].push_back(a);}for (int n = 0; n < N; n++) {cin >> cost[n];}init();unsigned long long total = 0;cin >> M;for (int m = 0; m < M; m++) {int a, b, c, p;cin >> a;cin >> b;cin >> c;p = solve(a, b);total += (cost_sum[a] + cost_sum[b] - (cost_sum[p] * 2) + cost[p]) * c;}cout << total << endl;}