結果

問題 No.386 貪欲な領主
ユーザー zaki_joho
提出日時 2019-03-19 17:26:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 160 ms / 2,000 ms
コード長 6,276 bytes
コンパイル時間 2,112 ms
コンパイル使用メモリ 188,832 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2024-09-14 01:00:19
合計ジャッジ時間 3,773 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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

#include "bits/stdc++.h"
using namespace std;
struct RangeMinimumQuery
{
using type = int;
static type id() { return INT_MAX; }
static type op(const type &l, const type &r) { return std::min(l, r); }
};
struct RangeMaximumQuery
{
using type = int;
static type id() { return -INT_MAX; }
static type op(const type &l, const type &r) { return std::max(l, r); }
};
struct RangeSumQuery
{
using type = long long;
static type id() { return 0; }
static type op(const type &l, const type &r) { return l + r; }
};
template <typename M>
class SegmentTree
{
using T = typename M::type;
int n;
std::vector<T> node;
public:
// v
SegmentTree(const std::vector<T> &v)
{
// n v.size() 2
n = 1;
while (n < int(v.size()))
n *= 2;
node.resize(2 * n, M::id());
// i -> 2*i+1, 2*i+2 , -> (i-1)/2
for (int i = 0; i < int(v.size()); i++)
node[i + n] = v[i];
for (int i = n - 1; i >= 0; i--)
node[i] = M::op(node[2 * i], node[2 * i + 1]);
}
// Monoid::id
SegmentTree(int _n)
{
// n v.size() 2
n = 1;
while (n < _n)
n *= 2;
node.resize(2 * n, M::id());
}
// x val
void update(int x, T val)
{
x += n;
node[x] = val;
while (x >>= 1)
{
node[x] = M::op(node[2 * x], node[2 * x + 1]);
}
}
// v[x] M::op(v[x], val)
void operation(int x, T val)
{
x += n;
node[x] = M::op(node[x], val);
while (x >>= 1)
{
node[x] = M::op(node[2 * x], node[2 * x + 1]);
}
}
// [a, b] op
T query(int l, int r)
{
l += n;
r += n;
T retl = M::id(), retr = M::id();
while (l < r)
{
if (l & 1)
retl = M::op(retl, node[l++]);
if (r & 1)
retr = M::op(node[--r], retr);
l >>= 1;
r >>= 1;
}
return M::op(retl, retr);
}
};
// http://beet-aizu.hatenablog.com/entry/2017/12/12/235950
struct HLDecomposition
{
int n, pos;
vector<vector<int>> G;
vector<int> vid, head, sub, hvy, par, dep, inv, type;
HLDecomposition() {}
HLDecomposition(int sz) : n(sz), pos(0), G(n),
vid(n, -1), head(n), sub(n, 1), hvy(n, -1),
par(n), dep(n), inv(n), type(n) {}
void add_edge(int u, int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
void build(vector<int> rs = vector<int>(1, 0))
{
int c = 0;
for (int r : rs)
{
dfs(r);
bfs(r, c++);
}
}
void dfs(int rt)
{
using T = pair<int, int>;
stack<T> st;
par[rt] = -1;
dep[rt] = 0;
st.emplace(rt, 0);
while (!st.empty())
{
int v = st.top().first;
int &i = st.top().second;
if (i < (int)G[v].size())
{
int u = G[v][i++];
if (u == par[v])
continue;
par[u] = v;
dep[u] = dep[v] + 1;
st.emplace(u, 0);
}
else
{
st.pop();
int res = 0;
for (int u : G[v])
{
if (u == par[v])
continue;
sub[v] += sub[u];
if (res < sub[u])
res = sub[u], hvy[v] = u;
}
}
}
}
void bfs(int r, int c)
{
int &k = pos;
queue<int> q({r});
while (!q.empty())
{
int h = q.front();
q.pop();
for (int i = h; i != -1; i = hvy[i])
{
type[i] = c;
vid[i] = k++;
inv[vid[i]] = i;
head[i] = h;
for (int j : G[i])
if (j != par[i] && j != hvy[i])
q.push(j);
}
}
}
// for_each(vertex)
// [l,r] <- attention!!
void for_each(int u, int v, const function<void(int, int)> &f)
{
while (1)
{
if (vid[u] > vid[v])
swap(u, v);
f(max(vid[head[v]], vid[u]), vid[v]);
if (head[u] != head[v])
v = par[head[v]];
else
break;
}
}
// for_each(edge)
// [l,r] <- attention!!
void for_each_edge(int u, int v, const function<void(int, int)> &f)
{
while (1)
{
if (vid[u] > vid[v])
swap(u, v);
if (head[u] != head[v])
{
f(vid[head[v]], vid[v]);
v = par[head[v]];
}
else
{
if (u != v)
f(vid[u] + 1, vid[v]);
break;
}
}
}
int lca(int u, int v)
{
while (1)
{
if (vid[u] > vid[v])
swap(u, v);
if (head[u] == head[v])
return u;
v = par[head[v]];
}
}
int distance(int u, int v)
{
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
};
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
SegmentTree<RangeSumQuery> st(n);
HLDecomposition hl(n);
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
hl.add_edge(a, b);
// hl.add_edge(b, a);
}
hl.build();
for (int i = 0; i < n; i++)
{
int index, u;
cin >> u;
index = hl.vid[i];
st.update(index, u);
}
int m;
cin >> m;
long long ret = 0;
while (m--)
{
long long a, b, c;
cin >> a >> b >> c;
// a = hl.vid[a];
// b = hl.vid[b];
hl.for_each(a, b, [&](int l, int r) { ret += c * st.query(l, r + 1); });
}
cout << ret << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0