結果

問題 No.386 貪欲な領主
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2020-06-02 20:57:19
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 3,357 bytes
コンパイル時間 1,838 ms
コンパイル使用メモリ 168,732 KB
実行使用メモリ 10,100 KB
最終ジャッジ日時 2023-08-16 03:24:31
合計ジャッジ時間 6,014 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:110:10: warning: ‘m’ is used uninitialized in this function [-Wuninitialized]
     scanf("%d",m);
     ~~~~~^~~~~~~~

ソースコード

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() {
    scanf("%d",&n);
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d",&a,&b);
        g[a].push_back({b, 0});
        g[b].push_back({a, 0});
    }
    cost.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d",&cost[i]);
    }
    int m;
    scanf("%d",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;
        scanf("%d %d %d",&a,&b,&c);
        ans += ll(c) * (lca.dist(a, b) + cost[a] + cost[b] - cost[lca.lca(a, b)]);
    }
    printf("%d\n",ans);
    return 0;
}
0