結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2019-03-11 16:37:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 402 ms / 2,000 ms |
コード長 | 2,250 bytes |
コンパイル時間 | 1,787 ms |
コンパイル使用メモリ | 172,168 KB |
実行使用メモリ | 29,480 KB |
最終ジャッジ日時 | 2024-06-23 15:37:20 |
合計ジャッジ時間 | 4,814 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;#pragma GCC optimize ("O3")#define int long long#define rep(i,n) for(int i=0;i<(int)(n);i++)#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define all(x) (x).begin(),(x).end()#define pb push_back#define mp make_pair#define mt make_tupletypedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<ll, ll> pll;typedef vector<ll> vl;const int inf = 1e9;const ll linf = 1LL<<60;const ll mod = 1e9 + 7;const double eps = 1e-9;/*{}*/class LowestCommonAncestor{public:int n, h;vector<vector<int>> g, par;vector<int> dep;vi cost;LowestCommonAncestor(){}LowestCommonAncestor(int n) : n(n), g(n), dep(n), cost(n){h = 1;while((1<<h) <= n) h++;par.assign(h, vector<int>(n, -1));}void add_edge(int u, int v){g[u].push_back(v);g[v].push_back(u);}void dfs(int v, int p, int d, int c, vi& u){par[0][v] = p;dep[v] = d;cost[v] = c+u[v];for(int to : g[v]){if(to != p) dfs(to, v, d+1, c+u[v], u);}}void build(vi& u, int r = 0){dfs(r, -1, 0, 0, u);for(int k = 0; k+1 < h; 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 lca(int u, int v){if(dep[u] > dep[v]) swap(u, v);for(int k = 0; k < h; k++){if((dep[v] - dep[u])>>k & 1){v = par[k][v];}}if(u == v) return u;for(int k = h-1; k >= 0; k--){if(par[k][u] != par[k][v]){u = par[k][u];v = par[k][v];}}return par[0][u];}int dist(int u, int v){return dep[u]+dep[v]-dep[lca(u, v)]*2;}int calc(int u, int v, vi& w){return cost[u]+cost[v]-cost[lca(u,v)]*2+w[lca(u,v)];}};signed main(){int n;cin >> n;LowestCommonAncestor lca(n);rep(i, n-1){int a, b;cin >> a >> b;lca.add_edge(a, b);}vi u(n);rep(i, n) cin >> u[i];lca.build(u);int m;cin >> m;int ans = 0;rep(i, m){int a, b, c;cin >> a >> b >> c;ans += lca.calc(a, b, u)*c;}cout << ans << endl;return 0;}