結果

問題 No.386 貪欲な領主
ユーザー utouto97utouto97
提出日時 2019-03-11 10:50:46
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,348 bytes
コンパイル時間 1,474 ms
コンパイル使用メモリ 153,736 KB
実行使用メモリ 24,332 KB
最終ジャッジ日時 2023-09-05 20:03:29
合計ジャッジ時間 5,798 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using 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)
  {
    int l = lca(u, v);
    int p = par[0][l];
    int res = cost[u]+cost[v];
    res -= w[l];
    if(p != -1) res -= cost[p]*2;
    return res;
  }
};

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 << lca.calc(a, b, u) << endl;
  }

  cout << ans << endl;

  return 0;
}
0