結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2017-07-22 16:17:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 181 ms / 2,000 ms |
コード長 | 1,054 bytes |
コンパイル時間 | 1,537 ms |
コンパイル使用メモリ | 171,100 KB |
実行使用メモリ | 22,528 KB |
最終ジャッジ日時 | 2024-10-09 09:56:25 |
合計ジャッジ時間 | 3,996 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>#define rep(i,n)for(int i=0;i<(n);i++)using namespace std;typedef long long ll;vector<int>E[100000];int par[18][100000],depth[100000],u[100000];ll sum[100000];void dfs(int v,int p,int d){if(p==-1)sum[v]=u[v];else sum[v]=sum[p]+u[v];par[0][v]=p;depth[v]=d;for(int u:E[v]){if(u!=p)dfs(u,v,d+1);}}int lca(int u,int v){if(depth[u]>depth[v])swap(u,v);rep(i,18){if((depth[v]-depth[u])>>i&1)v=par[i][v];}if(u==v)return u;for(int i=17;i>=0;i--){if(par[i][u]!=par[i][v]){u=par[i][u];v=par[i][v];}}return par[0][u];}int main(){int n;scanf("%d",&n);rep(i,n-1){int a,b;scanf("%d%d",&a,&b);E[a].push_back(b);E[b].push_back(a);}rep(i,n)scanf("%d",&u[i]);dfs(0,-1,0);for(int i=1;i<18;i++)rep(j,n){if(par[i-1][j]==-1)par[i][j]=-1;else par[i][j]=par[i-1][par[i-1][j]];}int m;scanf("%d",&m);ll ans=0;rep(i,m){int a,b,c;scanf("%d%d%d",&a,&b,&c);int p=lca(a,b);ans+=(sum[a]+sum[b]-(par[0][p]==-1?0:sum[par[0][p]])-sum[p])*c;}printf("%lld\n",ans);}