結果

問題 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;
}
0