結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2020-02-23 17:18:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 325 ms / 2,000 ms |
コード長 | 991 bytes |
コンパイル時間 | 575 ms |
コンパイル使用メモリ | 71,200 KB |
実行使用メモリ | 27,508 KB |
最終ジャッジ日時 | 2024-10-10 04:45:41 |
合計ジャッジ時間 | 3,616 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
コンパイルメッセージ
main.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 41 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>using namespace std;int N;vector<int>G[1<<17];int pa[20][1<<17];int cumsum[1<<17];int depth[1<<17];int U[1<<17];void dfs(int u,int p,int cu,int d){cumsum[u]=cu+=U[u];pa[0][u]=p;depth[u]=d++;for(int v:G[u]){if(v!=p){dfs(v,u,cu,d);}}}int lca(int u,int v){if(depth[u]<depth[v])u^=v^=u^=v;for(int k=0;k<20;k++){if(depth[u]-depth[v]>>k&1)u=pa[k][u];}if(u==v)return u;for(int k=20;k--;){if(pa[k][u]!=pa[k][v]){u=pa[k][u];v=pa[k][v];}}return pa[0][u];}main(){cin>>N;for(int i=1;i<N;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}for(int i=0;i<N;i++)cin>>U[i];dfs(0,-1,0,0);for(int k=1;k<20;k++)for(int i=0;i<N;i++){if(pa[k-1][i]>=0)pa[k][i]=pa[k-1][pa[k-1][i]];else pa[k][i]=-1;}int M;cin>>M;long ans=0;for(;M--;){int u,v,c;cin>>u>>v>>c;int g=lca(u,v);ans+=c*(cumsum[u]+cumsum[v]-2*cumsum[g]+U[g]);}cout<<ans<<endl;}