結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 myun-plusplus
|
| 提出日時 | 2020-12-15 17:35:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,679 bytes |
| コンパイル時間 | 2,858 ms |
| コンパイル使用メモリ | 205,572 KB |
| 最終ジャッジ日時 | 2025-01-17 01:06:21 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 18 TLE * 1 |
ソースコード
//#define ATCODER_EX_DEBUG
#include <type_traits>
#include <utility>
#include <vector>
#include <cstddef>
#include <iostream>
namespace atcoder_ex {
template<bool Is_Evertable = false, class S = std::nullptr_t, S(*op)(S, S) = nullptr, S(*e)() = nullptr,
class F = std::nullptr_t, S(*mapping)(F, S) = nullptr, F(*composition)(F, F) = nullptr, F(*id)() = nullptr>
class link_cut_tree {
static constexpr bool is_pull_type_v = !std::is_same_v<S, std::nullptr_t>;
static constexpr bool is_push_type_v = !std::is_same_v<F, std::nullptr_t>;
struct no_value_base {};
struct sum_base {
sum_base() : value(e()), sum(e()) {}
S value, sum;
};
struct sum_apply_base {
sum_apply_base() : value(e()), sum(e()), apply(id()) {}
S value, sum;
F apply;
};
struct non_evertable_base {};
struct evertable_base {
evertable_base() : rev(false) {}
bool rev;
};
using v_base = std::conditional_t<is_push_type_v, sum_apply_base,
std::conditional_t<is_pull_type_v, sum_base, no_value_base>>;
using e_base = std::conditional_t<Is_Evertable, evertable_base, non_evertable_base>;
struct splay_tree_node : public v_base, public e_base {
splay_tree_node() : v_base(), e_base(), left(-1), right(-1), parent(-1) {}
int left, right, parent;
};
using node = splay_tree_node;
public:
link_cut_tree() : link_cut_tree(0) {}
explicit link_cut_tree(int n) : m_size(n), m_nodes(n) {}
void link(int v, int p) {
expose(v);
splay(v);
expose(p);
splay(v);
m_nodes[p].right = v;
m_nodes[v].parent = p;
pull(p);
}
void cut(int v) {
expose(v);
splay(v);
int p = m_nodes[v].left;
m_nodes[v].left = -1;
m_nodes[p].parent = -1;
pull(v);
}
template<bool Always_True = true, std::enable_if_t<Always_True && Is_Evertable>* = nullptr>
void evert(int v) {
expose(v);
splay(v);
std::swap(m_nodes[v].left, m_nodes[v].right);
m_nodes[v].rev = true;
}
int lowest_common_ancester(int u, int v) {
expose(u);
return expose(v);
}
template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
S get(int v) {
push_down_from_top(v);
splay(v);
return m_nodes[v].value;
}
template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
void set(int v, S x) {
push_down_from_top(v);
splay(v);
m_nodes[v].value = x;
pull(v);
}
template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
S prod(int u, int v) {
expose(u);
int w = expose(v);
splay(u);
splay(w);
S sum = m_nodes[w].value;
if (u != w) {
sum = op(m_nodes[u].sum, sum);
}
if (int r = m_nodes[w].right; r != -1) {
sum = op(sum, m_nodes[r].sum);
}
return sum;
}
template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
void apply(int v, F f) {
push_down_from_top(v);
m_nodes[v].value = mapping(f, m_nodes[v].value);
pull_to_top(v);
}
template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
void apply(int u, int v, F f) {
expose(u);
int w = expose(v);
splay(u);
splay(w);
m_nodes[w].value = mapping(f, m_nodes[w].value);
if (u != w) {
apply_to_node(u, f);
}
if (int r = m_nodes[w].right; r != -1) {
apply_to_node(r, f);
}
}
void debug() {
std::vector<bool> visited(m_size);
auto dfs = [&](auto self, int v, int p) -> void {
visited[v] = true;
S sum = m_nodes[v].value;
if (int l = m_nodes[v].left; l != -1) {
self(self, l, v);
sum = op(m_nodes[l].sum, sum);
}
if (int r = m_nodes[v].right; r != -1) {
self(self, r, v);
sum = op(sum, m_nodes[r].sum);
}
bool ok = m_nodes[v].sum == sum;
if (!ok) {
std::cout << v << std::endl;
}
};
for (int v = 0; v < m_size; ++v) {
if (visited[v]) continue;
if (!is_splay_tree_root(v)) continue;
dfs(dfs, v, -1);
}
}
private:
int expose(int v) {
int pre = -1;
for (int current = v; current != -1; current = m_nodes[current].parent) {
push_down_from_top(current);
splay(current);
m_nodes[current].right = pre;
pull(current);
pre = current;
}
return pre;
}
void splay(int v) {
while (!is_splay_tree_root(v)) {
int p = m_nodes[v].parent;
int gp = m_nodes[p].parent;
if (!is_splay_tree_root(p)) {
int ggp = m_nodes[gp].parent;
if (ggp != -1) {
if (gp == m_nodes[ggp].left) m_nodes[ggp].left = v;
else if (gp == m_nodes[ggp].right) m_nodes[ggp].right = v;
}
m_nodes[v].parent = ggp;
if (v == m_nodes[p].left && p == m_nodes[gp].right) {
int b = m_nodes[v].right, c = m_nodes[v].left;
m_nodes[v].right = p;
m_nodes[p].parent = v;
m_nodes[v].left = gp;
m_nodes[gp].parent = v;
m_nodes[p].left = b;
if (b != -1) m_nodes[b].parent = p;
m_nodes[gp].right = c;
if (c != -1) m_nodes[c].parent = gp;
}
else if (v == m_nodes[p].right && p == m_nodes[gp].left) {
int b = m_nodes[v].left, c = m_nodes[v].right;
m_nodes[v].left = p;
m_nodes[p].parent = v;
m_nodes[v].right = gp;
m_nodes[gp].parent = v;
m_nodes[p].right = b;
if (b != -1) m_nodes[b].parent = p;
m_nodes[gp].left = c;
if (c != -1) m_nodes[c].parent = gp;
}
else if (v == m_nodes[p].left && p == m_nodes[gp].left) {
int b = m_nodes[v].right, c = m_nodes[p].right;
m_nodes[v].right = p;
m_nodes[p].parent = v;
m_nodes[p].right = gp;
m_nodes[gp].parent = p;
m_nodes[p].left = b;
if (b != -1) m_nodes[b].parent = p;
m_nodes[gp].left = c;
if (c != -1) m_nodes[c].parent = gp;
}
else {
int b = m_nodes[v].left, c = m_nodes[p].left;
m_nodes[v].left = p;
m_nodes[p].parent = v;
m_nodes[p].left = gp;
m_nodes[gp].parent = p;
m_nodes[p].right = b;
if (b != -1) m_nodes[b].parent = p;
m_nodes[gp].right = c;
if (c != -1) m_nodes[c].parent = gp;
}
pull(gp);
pull(p);
pull(v);
}
else {
if (v == m_nodes[p].left) {
int x = m_nodes[v].right;
m_nodes[p].left = x;
if (x != -1) m_nodes[x].parent = p;
m_nodes[v].parent = m_nodes[p].parent;
m_nodes[v].right = p;
m_nodes[p].parent = v;
}
else {
int x = m_nodes[v].left;
m_nodes[p].right = x;
if (x != -1) m_nodes[x].parent = p;
m_nodes[v].parent = m_nodes[p].parent;
m_nodes[v].left = p;
m_nodes[p].parent = v;
}
pull(p);
pull(v);
}
}
}
inline int is_splay_tree_root(int v) const {
int p = m_nodes[v].parent;
return p == -1 || (m_nodes[p].left != v && m_nodes[p].right != v);
}
template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
inline void pull(int v) {
S sum = m_nodes[v].value;
if (int l = m_nodes[v].left; l != -1) sum = op(m_nodes[l].sum, sum);
if (int r = m_nodes[v].right; r != -1) sum = op(sum, m_nodes[r].sum);
m_nodes[v].sum = sum;
}
template<bool Always_True = true, std::enable_if_t<Always_True && !is_pull_type_v>* = nullptr>
inline void pull(int) {}
template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
inline void update_push(int v) { pull(v); }
template<bool Always_True = true, std::enable_if_t<Always_True && !is_push_type_v>* = nullptr>
inline void update_push(int) {}
template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
inline void push(int v) {
if (m_nodes[v].apply == id()) return;
if (int l = m_nodes[v].left; l != -1) {
apply_to_node(l, m_nodes[v].apply);
}
if (int r = m_nodes[v].right; r != -1) {
apply_to_node(r, m_nodes[v].apply);
}
m_nodes[v].apply = id();
if constexpr (Is_Evertable) {
eval_rev(v);
}
}
template<bool Always_True = true, std::enable_if_t<Always_True && !is_push_type_v>* = nullptr>
inline void push(int v) {
if constexpr (Is_Evertable) {
eval_rev(v);
}
}
template<bool Always_True = true, std::enable_if_t<Always_True&& is_push_type_v>* = nullptr>
inline void apply_to_node(int v, F f) {
m_nodes[v].value = mapping(f, m_nodes[v].value);
m_nodes[v].sum = mapping(f, m_nodes[v].sum);
m_nodes[v].apply = composition(f, m_nodes[v].apply);
}
template<bool Always_True = true, std::enable_if_t<Always_True && Is_Evertable>* = nullptr>
inline void eval_rev(int v) {
if (m_nodes[v].rev) {
if (int l = m_nodes[v].left; l != -1) {
std::swap(m_nodes[l].left, m_nodes[l].right);
m_nodes[l].rev = true;
}
if (int r = m_nodes[v].right; r != -1) {
std::swap(m_nodes[r].left, m_nodes[r].right);
m_nodes[r].rev = true;
}
m_nodes[v].rev = false;
}
}
template<bool Always_True = true, std::enable_if_t<Always_True && !Is_Evertable>* = nullptr>
inline void eval_rev(int v) {}
void pull_to_top(int v) {
while (v != -1) {
pull(v);
v = m_nodes[v].parent;
}
}
void update_push_to_top(int v) {
while (v != -1) {
update_push(v);
v = m_nodes[v].parent;
}
}
void push_down_from_top(int v) {
if (m_nodes[v].parent != -1) {
push_down_from_top(m_nodes[v].parent);
}
push(v);
}
private:
int m_size;
std::vector<node> m_nodes;
};
} // namespace atcoder_ex
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = std::pair<ll, int>;
constexpr P op(P l, P r) { return P(l.first + r.first, l.second + r.second); }
constexpr P e() { return P(0, 1); }
constexpr P mapping(int l, P r) { return P(r.first + (ll)l * r.second, r.second); }
constexpr int composition(int l, int r) { return l + r; }
constexpr int id() { return 0; }
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int N;
cin >> N;
vector<vector<int>> tree(N);
for (int i = 0; i < N - 1; ++i) {
int u, v;
cin >> u >> v;
u--; v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
atcoder_ex::link_cut_tree<false, P, op, e, int, mapping, composition, id> lct(N);
auto dfs = [&](auto self, int v, int p) -> void {
for (int u : tree[v]) {
if (u == p) continue;
lct.link(u, v);
self(self, u, v);
}
};
dfs(dfs, 0, -1);
int Q;
cin >> Q;
ll ans = 0;
for (int i = 0; i < Q; ++i) {
int a, b;
cin >> a >> b;
a--; b--;
lct.apply(a, b, 1);
ans += lct.prod(a, b).first;
}
cout << ans << endl;
}