結果

問題 No.386 貪欲な領主
コンテスト
ユーザー 🍮かんプリン
提出日時 2020-06-02 20:54:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,325 bytes
コンパイル時間 1,645 ms
コンパイル使用メモリ 184,144 KB
実行使用メモリ 38,732 KB
最終ジャッジ日時 2024-11-24 12:54:54
合計ジャッジ時間 27,397 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.06.02 20:54:11
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int n;
vector< vector< pair< int, int > > > g;
vector< int > cost;
void dfs(int v, int p = -1) {
    for (int i = 0; i < g[v].size(); i++) {
        if (g[v][i].first == p) {
            g[v][i].second = cost[p];
        } else {
            g[v][i].second = cost[v];
            dfs(g[v][i].first, v);
        }
    }
}
// 最近共通祖先(Doubling)
// verify : https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C
// <O(NlogN),O(lonN)>
struct LowestCommonAncestor {
private:
    struct edge {
        int to, cost;
        edge(int to, int cost) : to(to), cost(cost) {}
    };
    int n;
    int log;
    vector< vector< int > > parent;
    vector< int > dep;
    vector< vector< edge > > G;
    vector< ll > dis;  // root からの距離
    void dfs(const vector< vector< edge > >& G, int v, int p, int d, int di) {
        parent[0][v] = p;
        dep[v] = d;
        dis[v] = di;
        for (edge e : G[v]) {
            // if (to != p) dfs(G, to, v, d + 1);
            if (e.to != p) dfs(G, e.to, v, d + 1, di + e.cost);
        }
    }
public:
    LowestCommonAncestor(int n) : n(n) {
        G.resize(n);
    }
    void add_edge(int from, int to, int cost) {
        G[from].push_back(edge(to, cost));
        G[to].push_back(edge(from, cost));
    }
    // add_edge後にする
    void build(int root = 0) {
        log = log2(n) + 1;
        parent.resize(log, vector< int >(n));
        dep.resize(n);
        dis.resize(n);
        dfs(G, root, -1, 0, 0);
        for (int k = 0; k + 1 < log; k++) {
            for (int v = 0; v < G.size(); v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }
    int depth(int v) {
        return dep[v];
    }
    // O(logN)
    int lca(int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        for (int k = 0; k < log; k++)
            if ((dep[v] - dep[u]) >> k & 1) v = parent[k][v];
        if (u == v) return u;
        for (int k = log - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int dist(int u, int v) {
        // return dep[u] + dep[v] - 2 * dep[lca(u, v)];
        return dis[u] + dis[v] - 2 * dis[lca(u, v)];
    }
};
int main() {
    cin >> n;
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, 0});
        g[b].push_back({a, 0});
    }
    cost.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    int m;
    cin >> m;
    dfs(0);
    LowestCommonAncestor lca(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            lca.add_edge(i, g[i][j].first, g[i][j].second);
        }
    }
    lca.build();
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        ans += ll(c) * (lca.dist(a, b) + cost[a] + cost[b] - cost[lca.lca(a, b)]);
    }
    cout << ans << endl;
    return 0;
}
0