結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2018-04-01 15:32:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 412 ms / 2,000 ms |
コード長 | 3,076 bytes |
コンパイル時間 | 993 ms |
コンパイル使用メモリ | 106,772 KB |
実行使用メモリ | 28,928 KB |
最終ジャッジ日時 | 2024-06-26 05:27:33 |
合計ジャッジ時間 | 4,060 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
# 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;}