結果

問題 No.386 貪欲な領主
ユーザー suzuken_w
提出日時 2019-11-09 00:06:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 205 ms / 2,000 ms
コード長 2,641 bytes
コンパイル時間 2,356 ms
コンパイル使用メモリ 189,608 KB
実行使用メモリ 20,956 KB
最終ジャッジ日時 2024-09-15 03:05:46
合計ジャッジ時間 4,689 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
vector<ll> fare;
template<typename G>
struct DLCA{
const int Log;
vector<int> dep;
vector<ll> cost;
const G &g;
vector<vector<int>> table;
explicit DLCA(const G &g):g(g),dep(g.size()),Log(32-__builtin_clz(g.size())){
table.assign(Log,vector<int>(g.size(),-1));
cost.assign(g.size(),0);
}
//
void dfs(int idx,int par,int d){
table[0][idx]=par;
dep[idx]=d;
if(par!=-1)cost[idx]+=cost[par]+fare[idx];
else cost[idx]+=fare[idx];
for(auto &to:g[idx]){
if(to!=par)dfs(to,idx,d+1);
}
}
//
void build(){
dfs(0,-1,0);
for(int k=0;k<Log-1;k++){
for(int i=0;i<table[k].size();i++){
if(table[k][i]==-1)table[k+1][i]=-1;
else table[k+1][i]=table[k][table[k][i]];
}
}
}
//
int query(int u,int v){
if(dep[u]>dep[v])swap(u,v);
for(int i=Log-1;i>=0;i--){
if(dep[v]-dep[u]&(1<<i))v=table[i][v];
}
if(u==v)return u;
for(int i=Log-1;i>=0;i--){
if(table[i][u]!=table[i][v]){
u=table[i][u];
v=table[i][v];
}
}
return table[0][u];
}
//
int dist(int u,int v){
int par=query(u,v);
return abs(dep[u]-dep[par])+abs(dep[v]-dep[par]);
}
ll money(int u,int v){
int par=query(u,v);
return cost[u]+cost[v]-2*cost[par]+fare[par];
}
};
int main(){
int n;
cin>>n;
vector<vector<int>> graph(n);
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
fare.resize(n);
for(int i=0;i<n;i++){
cin>>fare[i];
}
DLCA<vector<vector<int>>>lca(graph);
lca.build();
int q;cin>>q;
ll ans=0;
while(q--){
ll a,b,c;
cin>>a>>b>>c;
ans+=(lca.money(a,b))*c;
}
cout<<ans<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0