結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2018-03-15 02:47:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 223 ms / 2,000 ms |
コード長 | 2,615 bytes |
コンパイル時間 | 1,728 ms |
コンパイル使用メモリ | 170,456 KB |
実行使用メモリ | 24,064 KB |
最終ジャッジ日時 | 2024-11-30 12:13:28 |
合計ジャッジ時間 | 3,958 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define all(x) (x).begin(),(x).end()#define pb push_back#define fi first#define se second#define dbg(x) cout<<#x" = "<<((x))<<endltemplate<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}//ノードの個数const int MAX_V = 100000;//ダブリングに必要なサイズ(log(MAX_V))const int MAX_LOG_V = 18;//木の隣接リスト表現vector<int> G[MAX_V];//根のノード番号int root = 0;//親を2^k回辿って到達するノード(根を通り過ぎる場合,-1)int parent[MAX_LOG_V][MAX_V];//根からの深さint depth[MAX_V];//現在vに注目、親はp、深さdvoid lca_dfs(int v, int p, int d){parent[0][v]=p;depth[v]=d;rep(i,G[v].size()){if(G[v][i]!=p){ //親でなければ子lca_dfs(G[v][i], v, d+1);}}}//初期化void lca_init(int V){//parent[0]とdepthの初期化lca_dfs(root, -1, 0);//parentの初期化for(int k=0; k+1<MAX_LOG_V; ++k){for(int v=0; v<V; ++v){if(parent[k][v] < 0) parent[k+1][v]=-1;else parent[k+1][v] = parent[k][parent[k][v]];}}}//uとvのLCAを求めるint lca(int u, int v){//uとvの深さが同じになるまで親を辿るif(depth[u] > depth[v]) swap(u,v);for(int k=0; k<MAX_LOG_V; ++k){if((depth[v]-depth[u])>>k & 1) v = parent[k][v];}if(u==v) return u;//二分探索でLCAを求めるfor(int k=MAX_LOG_V-1; k>=0; --k){if(parent[k][u] != parent[k][v]){u=parent[k][u];v=parent[k][v];}}return parent[0][u];}int par[MAX_V]={};ll dp[MAX_V]={};void dfs(int cur){for(int nx:G[cur])if(nx != par[cur]){par[nx] = cur;dp[nx] += dp[cur];dfs(nx);}}int main(){int n;scanf(" %d", &n);rep(i,n-1){int a,b;scanf(" %d %d", &a, &b);G[a].pb(b);G[b].pb(a);}lca_init(n);vector<int> u(n);rep(i,n){scanf(" %d", &u[i]);dp[i] += u[i];}par[0] = -1;dfs(0);int m;scanf(" %d", &m);ll ans = 0;while(m--){int a,b,c;scanf(" %d %d %d", &a, &b, &c);int x = lca(a,b);ans += (dp[a]+dp[b]-2*dp[x]+u[x])*c;}printf("%lld\n", ans);return 0;}