結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 kcvlex
|
| 提出日時 | 2019-07-10 14:27:44 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,124 ms / 2,000 ms |
| コード長 | 9,385 bytes |
| コンパイル時間 | 2,423 ms |
| コンパイル使用メモリ | 194,468 KB |
| 実行使用メモリ | 41,088 KB |
| 最終ジャッジ日時 | 2024-10-15 12:52:58 |
| 合計ジャッジ時間 | 13,583 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
template <typename Graph>
struct HeavyLightDecomposition {
ll root;
const Graph &graph;
V<ll> subtree_size, head, parent_node_idx, decomposed_id, component_id, heavy_edge_to;
HeavyLightDecomposition(const Graph &graph)
: root(0),
graph(graph),
subtree_size(graph.size()),
head(graph.size()),
parent_node_idx(graph.size()),
decomposed_id(graph.size()),
component_id(graph.size()),
heavy_edge_to(graph.size())
{
}
ll count_size(ll cur, ll pre) {
ll ret = 1;
parent_node_idx[cur] = pre;
ll max_size = 0, max_size_to = -1;
for(ll nxt : graph[cur]) {
if(nxt == pre) continue;
ll res = count_size(nxt, cur);
if(max_size < res) {
max_size = res;
max_size_to = nxt;
}
ret += res;
}
heavy_edge_to[cur] = max_size_to;
return subtree_size[cur] = ret;
}
ll get_decomposed_id(ll node) { return node == -1 ? -1 : decomposed_id[node]; }
void build_component(ll cur, ll pre, ll &decomposed_id_counter, ll &total_hl) {
decomposed_id[cur] = decomposed_id_counter++;
component_id[cur] = total_hl;
head[cur] = (get_decomposed_id(pre) == -1 ? cur :
component_id[cur] == component_id[pre] ? head[pre] : cur);
if(heavy_edge_to[cur] != -1) build_component(heavy_edge_to[cur], cur, decomposed_id_counter, total_hl);
for(ll nxt : graph[cur]) {
if(nxt == pre || nxt == heavy_edge_to[cur]) continue;
build_component(nxt, cur, decomposed_id_counter, ++total_hl);
}
}
void decompose() {
count_size(root, -1);
ll decomposed_id_counter = 0;
ll total_hl = 0;
build_component(root, -1, decomposed_id_counter, total_hl);
}
// careful : when query handle edges
template <typename T>
T query(ll n1, ll n2, const function<T(ll, ll)> &calc_component, T identity, const function<T(T, T)> &merge) {
T lval = identity, rval = identity;
T result = identity;
while(true) {
if(component_id[n1] != component_id[n2]) {
if(decomposed_id[n1] < decomposed_id[n2]) {
T tmp = calc_component(decomposed_id[head[n2]], decomposed_id[n2] + 1);
rval = merge(tmp, rval);
n2 = parent_node_idx[head[n2]];
} else {
T tmp = calc_component(decomposed_id[head[n1]], decomposed_id[n1] + 1);
lval = merge(lval, tmp);
n1 = parent_node_idx[head[n1]];
}
} else {
ll id1 = decomposed_id[n1];
ll id2 = decomposed_id[n2];
result = calc_component(min(id1, id2), max(id1, id2) + 1);
result = merge(lval, result);
result = merge(result, rval);
break;
}
}
return result;
}
void query(ll n1, ll n2, const function<void(ll, ll)> &calc_component) {
ll identity = 0;
auto merge = [&](ll a, ll b) { return 0; };
auto wrapper_calc = [&](ll a, ll b) { calc_component(a, b); return 0; };
query<ll>(n1, n2, wrapper_calc, identity, merge);
}
};
// solution for https://yukicoder.me/problems/no/399
template <typename T, typename L>
class LazySegmentTree{
private:
ll N;
T init_node;
L init_lazy;
vector<T> node;
vector<L> lazy;
vector<bool> lazy_flag;
function<T(T, T)> merge_node;
function<T(T, L)> apply_lazy_value;
function<L(L, L)> update_lazy_value;
function<L(ll, ll, L)> create_lazy_value;
function<L(L)> prop_lazy_value;
public:
LazySegmentTree(const vector<T> &v,
const T &init_node,
const L &init_lazy,
const decltype(merge_node) &merge_node,
const decltype(apply_lazy_value) &apply_lazy_value,
const decltype(update_lazy_value) &update_lazy_value,
const decltype(create_lazy_value) &create_lazy_value,
const decltype(prop_lazy_value) &prop_lazy_value = [](L v) { return v; })
: init_node(init_node),
init_lazy(init_lazy),
merge_node(merge_node),
apply_lazy_value(apply_lazy_value),
update_lazy_value(update_lazy_value),
create_lazy_value(create_lazy_value),
prop_lazy_value(prop_lazy_value)
{
ll tmp = 1;
while(tmp < v.size()) tmp *= 2;
N = tmp;
node.resize(2 * N - 1, init_node);
lazy.resize(2 * N - 1, init_lazy);
lazy_flag.resize(2 * N - 1, false);
for(ll i = 0; i < v.size(); i++) {
node[i + N - 1] = v[i];
}
for(ll i = N - 2; 0 <= i; i--) {
node[i] = merge_node(node[i * 2 + 1], node[i * 2 + 2]);
}
}
/*
* node[pos] -> [left, right)
*/
void lazy_eval(ll pos, ll left, ll right) {
if(!lazy_flag[pos]) {
return;
}
node[pos] = apply_lazy_value(node[pos], lazy[pos]);
lazy_flag[pos] = false;
/*
* whether the node is the bottom of tree or not.
*/
if(right - left > 1) {
for(ll idx = 2 * pos + 1; idx <= 2 * pos + 2; idx++) {
lazy[idx] = update_lazy_value(lazy[idx], prop_lazy_value(lazy[pos]));
lazy_flag[idx] = true;
}
}
lazy[pos] = init_lazy;
}
/*
* If you want to call this func from out of class, in many cases you don't have to change the args pos, node_left, node_right.
* Be careful that the range is half-open interval.
* [left, right), [node_left, node_right)
* @param left: lower limit of interval of query
* @param right: upper limit of interval of query
* @param val: the value gave from query
* @param node_left: lower limit of interval of the node points.
* @param node_right: upper limit of interval of the node points.
*/
void update_query(ll left, ll right, L val, ll pos = 0, ll node_left = 0, ll node_right = -1) {
if(node_right < 0) {
node_right = N;
}
/*
* Execute lazy evaluation.
*/
lazy_eval(pos, node_left, node_right);
/*
* If the node is out of inrerval, return.
*/
if(right <= node_left || node_right <= left) {
return;
}
/*
* If the node cover the interval complety, update this->lazy and execute lazy_eval.
* Else recursion.
*/
if(left <= node_left && node_right <= right) {
lazy[pos] = create_lazy_value(node_left, node_right, val);
lazy_flag[pos] = true;
lazy_eval(pos, node_left, node_right);
} else {
/*
* recursion
*/
update_query(left, right, val, 2 * pos + 1, node_left, (node_left + node_right) / 2);
update_query(left, right, val, 2 * pos + 2, (node_left + node_right) / 2, node_right);
node[pos] = merge_node(node[2 * pos + 1], node[2 * pos + 2]);
}
}
T get_query(ll left, ll right, ll pos = 0, ll node_left = 0, ll node_right = -1) {
if(node_right < 0) {
node_right = N;
}
/*
* Evaluate the node[pos]
*/
lazy_eval(pos, node_left, node_right);
if(node_right <= left || right <= node_left) {
return init_node;
}
if(left <= node_left && node_right <= right) {
return node[pos];
}
ll split = (node_left + node_right) / 2;
return merge_node(get_query(left, right, 2 * pos + 1, node_left, split),
get_query(left, right, 2 * pos + 2, split, node_right));
}
};
VV<ll> edges;
#define VERIFY
#ifdef VERIFY
int main() {
ll N;
cin >> N;
edges.resize(N);
for(ll i = 1; i < N; i++) {
ll u, v;
cin >> u >> v;
u--; v--;
edges[u].push_back(v);
edges[v].push_back(u);
}
HeavyLightDecomposition<VV<ll>> hld(edges);
hld.decompose();
LazySegmentTree<ll, ll> lst(V<ll>(N, 1), 0, 0,
[](ll a, ll b) { return a + b; },
[](ll a, ll b) { return a + b; },
[](ll a, ll b) { return a + b; },
[](ll l, ll r, ll v) { return (r - l) * v; },
[](ll v) { return v / 2; });
auto update = [&](ll a, ll b) { lst.update_query(a, b, 1); };
auto calc_tax = [&](ll a, ll b) { return lst.get_query(a, b); };
auto merge = [&](ll a, ll b) { return a + b; };
ll Q;
cin >> Q;
ll ans = 0;
while(Q--) {
ll a, b;
cin >> a >> b;
a--; b--;
ll val = hld.query<ll>(a, b, calc_tax, 0, merge);
ans += val;
hld.query(a, b, update);
}
cout << ans << endl;
return 0;
}
#endif