結果

問題 No.386 貪欲な領主
ユーザー utouto97utouto97
提出日時 2019-03-11 16:37:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 402 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 1,787 ms
コンパイル使用メモリ 172,168 KB
実行使用メモリ 29,480 KB
最終ジャッジ日時 2024-06-23 15:37:20
合計ジャッジ時間 4,814 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 402 ms
29,476 KB
testcase_05 AC 304 ms
24,996 KB
testcase_06 AC 320 ms
24,868 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 36 ms
6,940 KB
testcase_09 AC 5 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 3 ms
6,940 KB
testcase_13 AC 8 ms
6,944 KB
testcase_14 AC 323 ms
24,996 KB
testcase_15 AC 353 ms
29,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("O3")

#define int long long
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*{
}*/

class LowestCommonAncestor
{
public:
  int n, h;
  vector<vector<int>> g, par;
  vector<int> dep;
  vi cost;
  
  LowestCommonAncestor(){}

  LowestCommonAncestor(int n) : n(n), g(n), dep(n), cost(n)
  {
    h = 1;
    while((1<<h) <= n) h++;
    par.assign(h, vector<int>(n, -1));
  }

  void add_edge(int u, int v)
  {
    g[u].push_back(v);
    g[v].push_back(u);
  }

  void dfs(int v, int p, int d, int c, vi& u)
  {
    par[0][v] = p;
    dep[v] = d;
    cost[v] = c+u[v];

    for(int to : g[v]){
      if(to != p) dfs(to, v, d+1, c+u[v], u);
    }
  }

  void build(vi& u, int r = 0)
  {
    dfs(r, -1, 0, 0, u);

    for(int k = 0; k+1 < h; k++){
      for(int v = 0; v < n; v++){
        if(par[k][v] < 0) par[k+1][v] = -1;
        else par[k+1][v] = par[k][par[k][v]];
      }
    }
  }

  int lca(int u, int v)
  {
    if(dep[u] > dep[v]) swap(u, v);

    for(int k = 0; k < h; k++){
      if((dep[v] - dep[u])>>k & 1){
        v = par[k][v];
      }
    }

    if(u == v) return u;

    for(int k = h-1; k >= 0; k--){
      if(par[k][u] != par[k][v]){
        u = par[k][u];
        v = par[k][v];
      }
    }

    return par[0][u];
  }

  int dist(int u, int v)
  {
    return dep[u]+dep[v]-dep[lca(u, v)]*2;
  }

  int calc(int u, int v, vi& w)
  {
    return cost[u]+cost[v]-cost[lca(u,v)]*2+w[lca(u,v)];
  }
};

signed main()
{
  int n;
  cin >> n;

  LowestCommonAncestor lca(n);
  rep(i, n-1){
    int a, b;
    cin >> a >> b;
    lca.add_edge(a, b);
  }

  vi u(n);
  rep(i, n) cin >> u[i];

  lca.build(u);

  int m;
  cin >> m;

  int ans = 0;
  rep(i, m){
    int a, b, c;
    cin >> a >> b >> c;
    ans += lca.calc(a, b, u)*c;
  }

  cout << ans << endl;

  return 0;
}
0