結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2022-09-15 19:49:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 438 ms / 2,000 ms |
コード長 | 2,037 bytes |
コンパイル時間 | 1,865 ms |
コンパイル使用メモリ | 182,528 KB |
実行使用メモリ | 31,616 KB |
最終ジャッジ日時 | 2024-12-17 13:37:16 |
合計ジャッジ時間 | 5,515 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll =long long;#define all(v) v.begin(),v.end()#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,a,b) for(int i=a;i>=b;i--)ll INF=2e18;struct LCA {ll V;ll logV;vector<vector<ll>> G;ll root;vector<vector<ll>> parent;//いないなら-1vector<ll> depth;//コンストラクタLCA(ll V_) :V(V_) {root=0;ll k=1;logV=0;while(k<=V) {k*=2;logV++;}G=vector<vector<ll>> (V,vector<ll> (0));parent=vector<vector<ll>> (V,vector<ll> (logV,-1));depth=vector<ll> (V);}void dfs(ll v,ll p,ll d) {parent[v][0]=p;depth[v]=d;for(ll i=0;i<G[v].size();i++) {if(G[v][i]!=p) dfs(G[v][i],v,d+1);}}void init() {dfs(root,-1,0);for(ll k=0;k+1<logV;k++) {for(ll v=0;v<V;v++) {if(parent[v][k]<0) parent[v][k+1]=-1;else parent[v][k+1]=parent[parent[v][k]][k];}}}ll lca(ll u,ll v) {if(depth[u]>depth[v]) swap(u,v);for(ll k=0;k<logV;k++) {if(((depth[v]-depth[u])>>k)&1) {v=parent[v][k];}}if(u==v) return u;for(ll k=logV-1;k>=0;k--) {if(parent[u][k]!=parent[v][k]) {u=parent[u][k];v=parent[v][k];}}return parent[u][0];}};int main() {ll N;cin>>N;LCA p(N);for(ll i=0;i<N-1;i++) {ll a,b;cin>>a>>b;p.G[a].push_back(b);p.G[b].push_back(a);}p.init();vector<ll> U(N);for(ll i=0;i<N;i++) cin>>U[i];vector<ll> d(N,INF);queue<pair<ll,ll>> S;S.push({0,0});while(!S.empty()) {auto x=S.front();S.pop();if(d[x.first]!=INF) continue;d[x.first]=x.second+U[x.first];for(auto y:p.G[x.first]) {S.push({y,d[x.first]});}}ll M;cin>>M;ll ans=0;for(ll i=0;i<M;i++) {ll A,B,C;cin>>A>>B>>C;ll k=p.lca(A,B);ll count=d[A]+d[B]-2*d[k]+U[k];ans+=count*C;}cout<<ans<<endl;}