結果

問題 No.386 貪欲な領主
コンテスト
ユーザー mamekin
提出日時 2016-10-07 19:19:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 366 ms / 2,000 ms
コード長 3,546 bytes
コンパイル時間 1,227 ms
コンパイル使用メモリ 119,476 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2024-11-21 19:50:53
合計ジャッジ時間 3,686 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

template <class T>
class LowestCommonAncestor
{
private:
    vector<vector<int> > to; // ダブリング先のノード
    vector<int> depth;       // 根からの深さ
    vector<T> sum;           // 根までのノード値の合計
    int climb(int curr, int dist)
    {
        int i = 0;
        while(dist > 0){
            if(dist % 2 == 1)
                curr = to[curr][i];
            dist /= 2;
            ++ i;
        }
        return curr;
    }
public:
    LowestCommonAncestor(const vector<vector<int> >& edges, const vector<T>& val, int root)
    {
        int n = edges.size();
        to.assign(n, vector<int>());
        sum.assign(n, 0);
        depth.assign(n, 0);

        queue<pair<int, int> > q;
        q.push(make_pair(root, -1));
        sum[root] = val[root];

        int cnt = 0;
        while(!q.empty()){
            int m = q.size();
            while(--m >= 0){
                int curr, prev;
                tie(curr, prev) = q.front();
                q.pop();

                if(prev != -1){
                    to[curr].push_back(prev);
                    int j = prev;
                    for(unsigned k=0; k<to[j].size(); ++k){
                        j = to[j][k];
                        to[curr].push_back(j);
                    }
                }

                for(int next : edges[curr]){
                    if(next != prev){
                        depth[next] = depth[curr] + 1;
                        sum[next] += sum[curr] + val[next];
                        q.push(make_pair(next, curr));
                    }
                }
            }
            ++ cnt;
        }
    }
    // 2つのノードの最小共通祖先を取得
    int getAncestor(int a, int b)
    {
        int diff = depth[a] - depth[b];
        if(diff < 0)
            b = climb(b, -diff);
        else
            a = climb(a, diff);
        if(a == b)
            return a;

        for(int i=to[a].size()-1; i>=0; --i){
            if(i < (int)to[a].size() && to[a][i] != to[b][i]){
                a = to[a][i];
                b = to[b][i];
            }
        }
        return to[a][0];
    }
    // ノードの深さを取得
    int getDepth(int a)
    {
        return depth[a];
    }
    // 2つのノード間にあるノード値の合計を取得
    T getSum(int a, int b)
    {
        int c = getAncestor(a, b);
        T ans = sum[a] + sum[b] - sum[c];
        if(!to[c].empty()){
            int d = to[c][0];
            ans -= sum[d];
        }
        return ans;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<vector<int> > edges(n);
    for(int i=0; i<n-1; ++i){
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    vector<long long> u(n);
    for(int i=0; i<n; ++i)
        cin >> u[i];

    int m;
    cin >> m;
    LowestCommonAncestor<long long> lca(edges, u, 0);
    long long ans = 0;
    for(int i=0; i<m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        ans += lca.getSum(a, b) * c;
    }
    cout << ans << endl;

    return 0;
}
0