結果
| 問題 | No.399 動的な領主 |
| ユーザー |
 math_hiyoko
|
| 提出日時 | 2023-03-26 23:05:54 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 701 ms / 2,000 ms |
| コード長 | 5,943 bytes |
| コンパイル時間 | 1,691 ms |
| コンパイル使用メモリ | 130,304 KB |
| 実行使用メモリ | 34,512 KB |
| 最終ジャッジ日時 | 2024-09-19 10:03:45 |
| 合計ジャッジ時間 | 9,762 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
#include <atcoder/dsu.hpp>
#include <atcoder/lazysegtree.hpp>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
using namespace atcoder;
using namespace std;
using ll = long long;
class heavy_light_decomposition {
private:
int N_, count_edge_ = 0;
std::map<std::pair<int, int>, int> edge_idx_;
std::vector<std::pair<int, int>> edge_by_order_;
std::vector<int> sub_, depth_, parent_,
head_, order_, order_inverse_;
struct edge {int idx; int to;};
std::vector<std::vector<edge>> edge_;
bool build_flag_ = false;
atcoder::dsu union_find;
int calculate_tree_information(int v = 0, int p = -1){
sub_[v] = 1;
depth_[v] = p == -1 ? 0 : depth_[p] + 1;
parent_[v] = p;
if(!edge_[v].empty() && edge_[v][0].to == p) std::swap(edge_[v][0], edge_[v].back());
for(edge &e : edge_[v]){
if(e.to == p) continue;
sub_[v] += calculate_tree_information(e.to, v);
if(sub_[e.to] > sub_[edge_[v][0].to]) std::swap(e, edge_[v][0]);
}
return sub_[v];
}
void construct_heavy_leght_decomposition(int &i, int v = 0){
order_[v] = i;
order_inverse_[i++] = v;
for(edge e : edge_[v]){
if(e.to == parent_[v]) continue;
head_[e.to] = (e.to == edge_[v][0].to ? head_[v] : e.to);
construct_heavy_leght_decomposition(i, e.to);
}
return;
}
void build_(){
assert(N_ == count_edge_ + 1);
calculate_tree_information();
int i = 0;
construct_heavy_leght_decomposition(i);
build_flag_ = true;
return;
}
public:
heavy_light_decomposition(int N){
N_ = N;
edge_by_order_.resize(N);
sub_.resize(N);
depth_.resize(N);
parent_.resize(N);
head_.resize(N);
order_.resize(N);
order_inverse_.resize(N);
edge_.resize(N);
union_find = atcoder::dsu(N);
}
int add_edge(int v, int u){
assert(!union_find.same(v, u));
union_find.merge(v, u);
edge_[v].push_back({count_edge_, u});
edge_[u].push_back({count_edge_, v});
edge_idx_[{v, u}] = edge_idx_[{u, v}] = count_edge_;
edge_by_order_[count_edge_] = {v, u};
return count_edge_++;
}
std::pair<int, int> get_edge(int idx){
assert(idx < count_edge_);
return edge_by_order_[idx];
}
int get_edge_idx(int v, int u){
return edge_idx_.count({v, u}) ? edge_idx_[{v, u}] : -1;
}
int lca(int v, int u){
if(!build_flag_) build_();
while(head_[v] != head_[u]){
if(depth_[head_[v]] > depth_[head_[u]]) std::swap(v, u);
u = parent_[head_[u]];
}
int i = std::min(order_[v], order_[u]);
return order_inverse_[i];
}
int get_hldidx_vertex(int v){
if(!build_flag_) build_();
return order_[v];
}
std::vector<std::pair<int, int>> subtree_query(int v){
if(!build_flag_) build_();
return std::vector<std::pair<int, int>>{{order_[v], order_[v] + sub_[v]}};
}
std::vector<std::pair<int, int>> path_query_vertex(int v, int u){
if(!build_flag_) build_();
std::vector<std::pair<int, int>> res;
while(head_[v] != head_[u]){
if(depth_[head_[v]] > depth_[head_[u]]) std::swap(v, u);
res.emplace_back(order_[head_[u]], order_[u] + 1);
u = parent_[head_[u]];
}
if(order_[v] > order_[u]) std::swap(v, u);
res.emplace_back(order_[v], order_[u] + 1);
return res;
}
int get_hldidx_edge(int idx){
if(!build_flag_) build_();
auto [v, u] = edge_by_order_[idx];
if(v == parent_[u]) std::swap(v, u);
return order_[v] - 1;
}
int get_hldidx_edge(int v, int u){
if(!build_flag_) build_();
assert(edge_idx_.count({v, u}));
if(v == parent_[u]) std::swap(v, u);
return order_[v] - 1;
}
std::vector<std::pair<int, int>> path_query_edge(int v, int u){
if(!build_flag_) build_();
std::vector<std::pair<int, int>> res;
while(head_[v] != head_[u]){
if(depth_[head_[v]] > depth_[head_[u]]) std::swap(v, u);
res.emplace_back(order_[head_[u]] - 1, order_[u]);
u = parent_[head_[u]];
}
if(order_[v] > order_[u]) std::swap(v, u);
res.emplace_back(order_[v], order_[u]);
return res;
}
};
struct S{
int length;
ll sum;
};
S op(S a, S b){ return {a.length + b.length, a.sum + b.sum}; }
S e(){ return {0, 0LL}; }
using F = int;
S mapping(F f, S x){ return {x.length, ll(f) * x.length + x.sum}; }
F composition(F f, F g){ return f + g; }
F id(){ return 0LL; }
int main(){
int N;
cin >> N;
heavy_light_decomposition graph(N);
for(int i = 0; i < N - 1; i++){
int u, v;
cin >> u >> v;
u--; v--;
graph.add_edge(u, v);
}
int Q;
cin >> Q;
lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<S>(N, {1, 0}));
ll ans = 0;
for(int _ = 0; _ < Q; _++){
int A, B;
cin >> A >> B;
A--; B--;
for(auto [l, r] : graph.path_query_vertex(A, B)){
seg.apply(l, r, 1);
ans += seg.prod(l, r).sum;
}
}
cout << ans << '\n';
return 0;
}