-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tree-hld-vertex-1.test.cpp
42 lines (40 loc) · 1.09 KB
/
Tree-hld-vertex-1.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define PROBLEM "https://yukicoder.me/problems/no/399"
#include <vector>
#include <iostream>
#include <cassert>
#include <map>
#include <algorithm>
#include <stack>
#include <numeric>
#include <array>
using namespace std;
#include "../../lib/40-graph/Graph.cpp"
#include "../../lib/40-graph/StaticTree.cpp"
#include "../../lib/10-segment-tree/LazySegmentTree.cpp"
#include "../../lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAdd.cpp"
int main(void){
int N; cin >> N;
Graph<int> g(N);
for(int i=0;i<N-1;++i) {
int u,v; cin >> u >> v;
u--,v--;
g.make_bidirectional_edge(u,v,1);
}
auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).root(0).parent().child().subtree_size().heavy_light_decomposition().build();
LazySegmentTree<MonoidRangeFoldSumRangeOperateAdd<long long,long long>> seg(N);
int Q; cin >> Q;
long long ans = 0;
while(Q--) {
int a,b; cin >> a >> b;
a--,b--;
auto vp = tree.vertex_set_on_path(a,b);
for(auto& p:vp) {
int l = p.first, r = p.second+1;
int n = r-l;
ans += seg.fold(l,r)+n;
seg.operate(l,r,1);
}
}
cout << ans << endl;
return 0;
}