結果

問題 No.386 貪欲な領主
ユーザー utouto97
提出日時 2019-03-11 16:37:25
言語 C++11
(gcc 13.3.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0