結果

問題 No.386 貪欲な領主
コンテスト
ユーザー kappybar
提出日時 2020-07-12 22:28:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 463 ms / 2,000 ms
コード長 2,096 bytes
コンパイル時間 1,803 ms
コンパイル使用メモリ 177,556 KB
実行使用メモリ 27,008 KB
最終ジャッジ日時 2024-11-06 05:45:05
合計ジャッジ時間 5,383 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int v = 100005; //頂点の数
vector<vector<int>> tree(v,vector<int>()); //木
vector<vector<int>> parents; //parents[i][j] := i の　2^j　上の祖先
vector<int> depth(v,0); //rootからの深さ
vector<ll> u(v);
vector<ll> uu(v);

void init_dfs(int i,int before=-1,int d=0,ll uuu=0){
    uuu += u[i];
    parents[i][0] = before;
    depth[i] = d;
    uu[i] = uuu;
    for(int next:tree[i]){
        if(next == before) continue;
        init_dfs(next,i,d+1,uuu);
    }
}

void LCAinit(int root = 0){
    int k = 1;
    while((1<<k)<v) k ++;
    parents.assign(v,vector<int>(k,-1));
    init_dfs(root);
    for(int j = 0;j < k-1;j++){
        for(int i = 0;i < v;i++){
            if(parents[i][j] < 0){
                parents[i][j+1] = -1;
            }else{
                parents[i][j+1] = parents[parents[i][j]][j];
            }
        }
    }
}

int LCA(int x,int y){
    if(depth[x] < depth[y]) swap(x,y);
    int k = parents[0].size();
    for(int i = 0;i < k;i++){
        if((depth[x]-depth[y]) >> i & 1){
            x = parents[x][i];
        }
    }

    if(x == y) return x;
    for(int i = k-1;i >= 0 ;i--){
        if(parents[x][i] != parents[y][i]){
            x = parents[x][i];
            y = parents[y][i];
        }
    }
    return parents[x][0];
}

int main(){
    cin >> v;
    rep(i,v-1){
        int a,b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    rep(i,v){
        ll p;
        cin >> p;
        u[i] = p;
    }
    LCAinit();

    ll ans = 0;
    int m;
    cin >> m;
    rep(i,m){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        int lca = LCA(a,b);
        ll res = uu[a] + uu[b] - 2*uu[lca] + u[lca];
        ans += c * res;
    }
    cout << ans << endl;
    return 0;
}
0