結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2017-10-16 21:55:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 2,020 bytes |
コンパイル時間 | 693 ms |
コンパイル使用メモリ | 88,604 KB |
実行使用メモリ | 27,904 KB |
最終ジャッジ日時 | 2024-11-17 21:22:58 |
合計ジャッジ時間 | 2,870 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<queue>#include<vector>#include<functional>#include<cmath>#include<map>#include<stack>#include<set>#include<numeric>#include<limits>#include<iterator>#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()#define rep(i,n) for(int i=0; i<n; i++)using namespace std;typedef long long ll;typedef pair<int, int> pi;typedef pair<ll, ll> pl;typedef pair<ll, char> plc;#define MAX_N 100100#define MAX_LOG_N 30int N, root;ll ans;vector<int> g[MAX_N];int depth[MAX_N];int par[MAX_N][MAX_LOG_N];int U[MAX_N * 2];int sum[100100];void bfs() {queue<int> q;sum[0] = U[0];q.push(0);while (!q.empty()) {int i = q.front(); q.pop();for (int j : g[i])if (sum[j] == 0) {sum[j] = sum[i] + U[j];q.push(j);}}}void dfs(int v, int p, int d){par[v][0] = p;depth[v] = d;for (int i = 0; i < g[v].size(); i++){if (g[v][i] == p)continue;dfs(g[v][i], v, d + 1);}}void fill_table(){for (int i = 0; i < 30-1; i++){for (int j = 0; j < N; j++){if (par[j][i] == -1)par[j][i + 1] = -1;else par[j][i + 1] = par[par[j][i]][i];}}}int lca(int u, int v){int tmp_u = u, tmp_v = v;if (depth[u] > depth[v])swap(u, v);for (int i = 19; i >= 0; i--){if (((depth[v] - depth[u]) >> i) & 1) {v = par[v][i];}}if (u == v)return u;for (int i = 19; i >= 0; i--){if (par[u][i] != par[v][i]){u = par[u][i];v = par[v][i];}}return par[u][0];}int dist(int u, int v) {return depth[u] + depth[v] - 2 * depth[lca(u, v)];}int main(){int q;cin >> N;rep(i, N-1) {int x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}root = 0;dfs(root, -1, 0);fill_table();rep(i, N)cin >> U[i];bfs();cin >> q;rep(i, q) {int u, v,c;cin >> u >> v >> c;int p = lca(u, v);ans += (sum[u] + sum[v] - sum[p] * 2 + U[p]) * c;}cout << ans << endl;return 0;}