結果

問題 No.386 貪欲な領主
ユーザー haruteru
提出日時 2016-07-07 11:24:41
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 1,869 bytes
コンパイル時間 619 ms
コンパイル使用メモリ 64,844 KB
実行使用メモリ 24,244 KB
最終ジャッジ日時 2024-10-12 23:00:51
合計ジャッジ時間 3,821 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
using namespace std;
#define MAXN (100000+1)
#define MAXM (200000+1)
int N, M;
vector<int> tree[MAXN];
int cost[MAXN];
int cost_sum[MAXN];
int depth[MAXN];
int log_n;
vector<vector<int> > par;
void dfs(int v, int p, int c, int d)
{
par[0][v] = p;
depth[v] = d;
cost_sum[v] = cost[v] + c;
for (int i = 0; i < tree[v].size(); i++) {
if (tree[v][i] != p) {
dfs(tree[v][i], v, cost_sum[v], d+1);
}
}
}
void init()
{
while (N > (1 << log_n)) log_n++;
par = vector<vector<int> >(log_n, vector<int>(N));
dfs(0, -1, 0, 0);
for (int k = 0; k < log_n-1; 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 solve(int u, int v)
{
if (depth[u] > depth[v]) {
swap(u, v);
}
for (int k = 0; k < log_n; k++) {
if((depth[v] - depth[u]) >> k & 1)v = par[k][v];
}
if(u==v)return u;
for (int k = log_n-1; k >= 0; k--) {
if (par[k][u] != par[k][v]) {
u = par[k][u];
v = par[k][v];
}
}
return par[0][u];
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
for (int n = 0; n < (N-1); n++) {
int a, b;
cin >> a;
cin >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
for (int n = 0; n < N; n++) {
cin >> cost[n];
}
init();
unsigned long long total = 0;
cin >> M;
for (int m = 0; m < M; m++) {
int a, b, c, p;
cin >> a;
cin >> b;
cin >> c;
p = solve(a, b);
total += (cost_sum[a] + cost_sum[b] - (cost_sum[p] * 2) + cost[p]) * c;
}
cout << total << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0