結果

問題 No.386 貪欲な領主
コンテスト
ユーザー siman
提出日時 2021-10-28 19:12:12
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 392 ms / 2,000 ms
コード長 3,108 bytes
コンパイル時間 3,744 ms
コンパイル使用メモリ 146,116 KB
実行使用メモリ 35,336 KB
最終ジャッジ日時 2024-10-07 08:05:36
合計ジャッジ時間 6,237 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <map>
#include <queue>
#include <set>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

const int MAX_V = 500000;
typedef pair<int, ll> S;

struct Node {
  int v;
  int depth;

  Node(int v = -1, int depth = -1) {
    this->v = v;
    this->depth = depth;
  }

  bool operator<(const Node &n) const {
    return depth < n.depth;
  }
};

class StaticRMQ {
public:
  vector <Node> dat;
  int N;

  void init(int n) {
    N = 1;

    while (N < n) N *= 2;

    for (int i = 0; i < 2 * N - 1; ++i) {
      dat.push_back(Node(-1, MAX_V));
    }
  }

  void update(int k, Node a) {
    k += N - 1;
    dat[k] = a;

    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }

  ll find_min(int l, int r) {
    return query(l, r, 0, 0, N).v;
  }

private:

  Node query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return Node(-1, MAX_V);

    if (a <= l && r <= b) {
      return dat[k];
    } else {
      Node vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
      Node vr = query(a, b, k * 2 + 2, (l + r) / 2, r);

      return min(vl, vr);
    }
  }
};

class LCA {
public:
  vector<int> vs;
  vector<int> depth;
  vector<int> id;
  vector <vector<int> > G;
  StaticRMQ rmq;

  LCA(int N, int root, vector <vector<int> > _G) {
    G = _G;
    int k = 0;
    vs = vector<int>(2 * N - 1);
    depth = vector<int>(2 * N - 1);
    id = vector<int>(N, -1);
    dfs(root, -1, 0, k);
    rmq.init(k);

    for (int i = 0; i < k; ++i) {
      rmq.update(i, Node(vs[i], depth[i]));
    }
  }

  int find_parent(int u, int v) {
    return rmq.find_min(min(id[u], id[v]), max(id[u], id[v]));
  }

private:
  void dfs(int v, int p, int d, int &k) {
    id[v] = k;
    vs[k] = v;
    depth[k++] = d;

    for (int i = 0; i < G[v].size(); ++i) {
      if (G[v][i] != p) {
        dfs(G[v][i], v, d + 1, k);
        vs[k] = v;
        depth[k++] = d;
      }
    }
  }
};

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

  vector<int> U(N);
  for (int i = 0; i < N; ++i) {
    cin >> U[i];
  }

  int root = 0;

  ll cost[N];
  queue<S> que;
  que.push(S(root, U[root]));
  bool visited[N];
  memset(visited, false, sizeof(visited));
  while (not que.empty()) {
    S s = que.front();
    que.pop();

    if (visited[s.first]) continue;
    visited[s.first] = true;
    cost[s.first] = s.second;

    for (int u : G[s.first]) {
      que.push(S(u, s.second + U[u]));
    }
  }

  LCA lca(N, root, G);

  int M;
  cin >> M;
  int l, r, c;
  ll total_cost = 0;
  for (int i = 0; i < M; ++i) {
    cin >> l >> r >> c;
    int p = lca.find_parent(l, r);
    ll ans = 0;

    if (p != root) {
      ans = cost[l] + cost[r] - 2 * cost[p] + U[p];
    } else {
      ans = cost[l] + cost[r] - U[p];
    }

    total_cost += ans * c;
  }

  cout << total_cost << endl;

  return 0;
}
0