結果

問題 No.386 貪欲な領主
ユーザー tnakao0123tnakao0123
提出日時 2016-07-14 19:35:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 284 ms / 2,000 ms
コード長 2,081 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 92,000 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2024-04-22 18:02:48
合計ジャッジ時間 3,690 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,016 KB
testcase_01 AC 3 ms
5,760 KB
testcase_02 AC 3 ms
6,016 KB
testcase_03 AC 3 ms
6,016 KB
testcase_04 AC 284 ms
17,024 KB
testcase_05 AC 220 ms
17,664 KB
testcase_06 AC 223 ms
17,536 KB
testcase_07 AC 5 ms
6,016 KB
testcase_08 AC 35 ms
7,040 KB
testcase_09 AC 7 ms
5,888 KB
testcase_10 AC 3 ms
5,760 KB
testcase_11 AC 3 ms
6,016 KB
testcase_12 AC 4 ms
6,144 KB
testcase_13 AC 9 ms
6,144 KB
testcase_14 AC 227 ms
17,536 KB
testcase_15 AC 235 ms
17,152 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 386.cc: No.386 貪欲な領主 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int BN = 17;

/* typedef */

typedef long long ll;
typedef vector<int> vi;

struct Stat {
  int i, p, d;
  Stat() {}
  Stat(int _i, int _p, int _d): i(_i), p(_p), d(_d) {}
};

/* global variables */

vi nbrs[MAX_N];
int us[MAX_N], ds[MAX_N], prts[MAX_N][BN];
ll usums[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int ai, bi;
    cin >> ai >> bi;
    nbrs[ai].push_back(bi);
    nbrs[bi].push_back(ai);
  }
  for (int i = 0; i < n; i++) cin >> us[i];

  ds[0] = 0;
  prts[0][0] = -1;
  usums[0] = us[0];

  queue<Stat> q;
  q.push(Stat(0, -1, 0));

  while (! q.empty()) {
    Stat u = q.front(); q.pop();
    vi &nbru = nbrs[u.i];
    int vd = u.d + 1;

    for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &vi = *vit;
      if (vi != u.p) {
	ds[vi] = vd;
	prts[vi][0] = u.i;
	usums[vi] = usums[u.i] + us[vi];
	q.push(Stat(vi, u.i, vd));
      }
    }
  }

  for (int i = 1; i < BN; i++)
    for (int j = 0; j < n; j++) {
      int &p = prts[j][i - 1];
      prts[j][i] = (p < 0) ? -1 : prts[p][i - 1];
    }
  
  int m;
  cin >> m;

  ll sum = 0;
  while (m--) {
    int ai, bi, ci;
    cin >> ai >> bi >> ci;

    int u = ai, v = bi;
    if (ds[u] > ds[v]) swap(u, v);

    for (int i = BN - 1; i >= 0; i--)
      if (((ds[v] - ds[u]) >> i) & 1) v = prts[v][i];

    if (u != v) {
      for (int i = BN - 1; i >= 0; i--)
	if (prts[u][i] != prts[v][i])
	  u = prts[u][i], v = prts[v][i];
      u = prts[u][0];
    }

    sum += (usums[ai] + usums[bi] - usums[u] * 2 + us[u]) * ci;
  }

  printf("%lld\n", sum);
  return 0;
}
0