結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-01 22:31:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 4,011 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 178,316 KB |
実行使用メモリ | 12,304 KB |
最終ジャッジ日時 | 2024-10-12 03:48:29 |
合計ジャッジ時間 | 3,620 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }class SchieberVishkinLCA {public:typedef unsigned Word;typedef int Vertex;private:static inline Word lowestOneBit(Word v) {return v & (~v + 1);}static inline Word highestOneBitMask(Word v) {v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;return v >> 1;}std::vector<Word> indices; //Vertex -> indexstd::vector<Word> maxHIndices; //Vertex -> indexstd::vector<Word> ancestorHeights; //Vertex -> Wordstd::vector<Vertex> pathParents; //index-1 -> Vertexpublic:void build(const std::vector<Vertex> &preorder, const std::vector<Vertex> &parents, Vertex root) {Vertex N = static_cast<Vertex>(preorder.size());ancestorHeights.resize(N);maxHIndices.resize(N);indices.resize(N);pathParents.resize(N);for(Vertex ix = 0; ix < N; ++ ix)indices[preorder[ix]] = ix + 1;for(Vertex i = 0; i < N; ++ i)maxHIndices[i] = indices[i];for(Vertex ix = N - 1; ix > 0; -- ix) {Vertex v = preorder[ix], parent = parents[v];if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))maxHIndices[parent] = maxHIndices[v];}ancestorHeights[root] = 0;for(Vertex ix = 1; ix < N; ++ ix) {Vertex v = preorder[ix], parent = parents[v];ancestorHeights[v] = ancestorHeights[parent] | lowestOneBit(maxHIndices[v]);}pathParents[0] = root;for(Vertex ix = 1; ix < N; ++ ix) {Vertex v = preorder[ix], parent = parents[v];if(maxHIndices[v] != maxHIndices[parent])pathParents[indices[v] - 1] = parent;elsepathParents[indices[v] - 1] = pathParents[indices[parent] - 1];}}Vertex query(Vertex v, Vertex u) const {Word Iv = maxHIndices[v], Iu = maxHIndices[u];Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);Vertex x, y;if(j == hIv) x = v;else {Word kMask = highestOneBitMask(ancestorHeights[v] & (j - 1));x = pathParents[(indices[v] & ~kMask | (kMask + 1)) - 1];}if(j == hIu) y = u;else {Word kMask = highestOneBitMask(ancestorHeights[u] & (j - 1));y = pathParents[(indices[u] & ~kMask | (kMask + 1)) - 1];}return indices[x] < indices[y] ? x : y;}};vector<int> t_parent;vi t_ord;void tree_getorder(const vector<vi> &g, int root) {int n = g.size();t_parent.assign(n, -1);t_ord.clear();vector<int> stk; stk.push_back(root);while(!stk.empty()) {int i = stk.back(); stk.pop_back();t_ord.push_back(i);for(int j = (int)g[i].size() - 1; j >= 0; j --) {int c = g[i][j];if(t_parent[c] == -1 && c != root)stk.push_back(c);elset_parent[i] = c;}}}int main() {int N;while(~scanf("%d", &N)) {vector<vector<int> > g(N);for(int i = 0; i < N - 1; ++ i) {int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}vector<int> U(N);for(int i = 0; i < N; ++ i)scanf("%d", &U[i]);tree_getorder(g, 0);SchieberVishkinLCA lca; lca.build(t_ord, t_parent, 0);vi sum(N, 0);for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {int i = t_ord[ix], p = t_parent[i];sum[i] = sum[p] + U[i];}int M;scanf("%d", &M);ll ans = 0;rep(ii, M) {int A; int B; int C;scanf("%d%d%d", &A, &B, &C);int L = lca.query(A, B);ans += (sum[A] + sum[B] - sum[L] * 2 + U[L]) * C;}printf("%lld\n", ans);}return 0;}