結果

問題 No.386 貪欲な領主
ユーザー tancahn2380tancahn2380
提出日時 2018-04-01 15:32:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 374 ms / 2,000 ms
コード長 3,076 bytes
コンパイル時間 1,031 ms
コンパイル使用メモリ 103,984 KB
実行使用メモリ 27,544 KB
最終ジャッジ日時 2023-09-08 12:14:34
合計ジャッジ時間 4,372 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,212 KB
testcase_01 AC 3 ms
7,332 KB
testcase_02 AC 4 ms
7,464 KB
testcase_03 AC 3 ms
7,216 KB
testcase_04 AC 374 ms
27,364 KB
testcase_05 AC 275 ms
22,860 KB
testcase_06 AC 275 ms
22,764 KB
testcase_07 AC 5 ms
7,316 KB
testcase_08 AC 37 ms
10,296 KB
testcase_09 AC 7 ms
7,348 KB
testcase_10 AC 4 ms
7,260 KB
testcase_11 AC 3 ms
7,256 KB
testcase_12 AC 5 ms
7,352 KB
testcase_13 AC 10 ms
7,764 KB
testcase_14 AC 276 ms
22,780 KB
testcase_15 AC 321 ms
27,544 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQ(c)     (c).erase(unique(ALL((c))),(c).end())
# define LOWER(s)    transform(ALL((s)),(s).begin(),TL<char>)
# define UPPER(s)    transform(ALL((s)),(s).begin(),TU<char>)
# define mp          make_pair
# define eb          emplace_back
# define FOR(i,a,b)  for(LL i=(a);i<(b);i++)
# define RFOR(i,a,b) for(LL i=(a);i>=(b);i--)
# define REP(i,n)    FOR(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int n, m, root;
vector<int> g[101010];
int depth[101010];
int par[101010][30];
LL u[101010];
LL cost[101010];

//木の深さを求める
void dfs(int v, int p, int d) {
	par[v][0] = p;
	depth[v] = d;
	if (p != -1) {
		cost[v] = cost[p] + u[v];
	}
	else {
		cost[v] = u[v];
	}
	for (int i = 0; i < g[v].size(); i++) {
		if (g[v][i] == p)continue;
		dfs(g[v][i], v, d + 1);
	}
}

//par[v][i]:=頂点vから2^i回親をたどった頂点（無かったら-1）
//vの親→par[v][0],vの親の親par[v][1]
//par[v][i+1]=par[par[v][i]]よりpar[~][i]が計算できればpar[~][i+1]も求まる
void fill_table() {
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < n; j++) {
			if (par[j][i] == -1)par[j][i + 1] = -1;
			else par[j][i + 1] = par[par[j][i]][i];
		}
	}
}


//頂点u,vのLCAを求める
int lca(int u, int v) {

	if (depth[u] > depth[v])swap(u, v);
	//深さをそろえるための処理
	for (int i = 19; i >= 0; i--) {
		if (((depth[v] - depth[u]) >> i) & 1) {
			v = par[v][i];
		}
	}

	if (u == v)return u;
	//ダブリング
	for (int i = 19; i >= 0; i--) {
		if (par[u][i] != par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}
LL ans = 0;
int main() {
	cin >> n;
	REP(i, n - 1) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
		root = a;
	}
	REP(i, n)cin >> u[i];
	dfs(root, -1, 0);
	fill_table();

	/*cout << root << endl;
	REP(i, n)cout << cost[i] << endl;
	system("pause");
	*/
	cin >> m;
	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		int lp = lca(a, b);
		ans += (cost[a] + cost[b] - cost[lp] * 2 + u[lp])*c;
	}
	cout << ans << endl;
	//system("pause");
	return 0;
}
0