#include #include #include #include #include using namespace std; template class Segment_Tree_Lazy{ private: //default values are set in the constractor const T default_value; //default (NULL) node value const T default_lazy_value; //default lazy value struct node{ T value; T lazy_value; bool lazy; int lb; int ub; node* par; node* lch; node* rch; node(T default_value, T default_lazy_value) : value(default_value), lazy_value(default_lazy_value), lazy(false), lb(0),ub(0), //this node covers [lb, rb) par(NULL),lch(NULL),rch(NULL){ } }; T evaluate(T left_val, T right_val){ //evaluate node value return left_val + right_val; //sum //return max(left_val, right_val); //max } T evaluate_node_and_lazy(T node_val, T lazy_val){ //evaluate node value and lazy value return node_val + lazy_val; //sum //return max(node_val, lazy_val); //max //return lazy_val; //fill } T evaluate_lazy_and_lazy(T old_val, T new_val){ return old_val + new_val; //sum //return new_val; //fill } void new_lazy(node* t, T add_value){ if(t==NULL) return; if(t->lazy){ t->lazy_value = evaluate_lazy_and_lazy(t->lazy_value, add_value); }else{ t->lazy_value = add_value; } t->lazy = true; } T lazy_to_value(node* t){ if(t->lazy) return t->lazy_value * (t->ub - t->lb); return default_lazy_value; } T get_value(node* t){ if(t==NULL) return default_value; return evaluate_node_and_lazy(t->value , lazy_to_value(t)); } vector v; node* root; int size; node* constract(node* t, int pos, int lb, int ub){ if(pos == 0){ t->par = t; } t->lb = lb; t->ub = ub; if(poslch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1); t->lch->par = t; t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub); t->rch->par = t; } return t; } void initialize(int size_){ size = 1; while(size < size_) size <<= 1; v = vector(size<<1, node(default_value, default_lazy_value)); root = constract(&v[0], 0, 0, size); } //propagate lazy value of node t to its children void push(node* t){ if(t==NULL) return; if(t->lazy){ if(t->lch != NULL){ //has child new_lazy(t->lch, t->lazy_value); new_lazy(t->rch, t->lazy_value); t->value = evaluate( get_value(t->lch), get_value(t->rch) ); }else{ t->value = get_value(t); } t->lazy_value = default_lazy_value; t->lazy = false; } } void range_add(int left, int right, T add_value, node* t){ if(t==NULL) return; if(t->ub <= left || right <= t->lb){ return; } push(t); if(left <= t->lb && t->ub <= right){ new_lazy(t, add_value); return; } //partialy covered range_add(left, right, add_value, t->lch); range_add(left, right, add_value, t->rch); t->value = evaluate( get_value(t->lch), get_value(t->rch) ); } //get value of [left,right) T get_range_value(int left, int right, node* t){ if(t==NULL) return default_value; if(t->ub <= left || right <= t->lb){ return default_value; } push(t); if(left <= t->lb && t->ub <= right){ return get_value(t); } T L = get_range_value(left, right, t->lch); T R = get_range_value(left, right, t->rch); return evaluate(L, R); } void lazy_update(node* t){ if(t->par != root){ lazy_update(t->par); } push(t); } public: //default node value must be set // sum : 0 // max : MIN_INF // min : MAX_INF // gcd : 1 Segment_Tree_Lazy(int size_, T default_value__ = 0, T default_lazy_value__ = 0) : default_value(default_value__), default_lazy_value(default_lazy_value__){ initialize(size_); } //node[pos] <= new_value void update(int pos, T new_value){ node* t = &v[pos + size-1]; lazy_update(t); t->value = new_value; while(t != root){ t = t->par; t->value = evaluate( get_value(t->lch), get_value(t->rch) ); } } //[l,r) += add_value void range_add(int left, int right, T add_value){ range_add(left, right, add_value, root); } //get value [left,right) T get_range_value(int left, int right){ return get_range_value(left, right, root); } void dbg(){ for(int i=0; i element; int depth; int parent_vertex; heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){} }; vector>& G; vector S; vector subtree_size; vector set_index; vector ele_index; private: int get_subtree_size(int pos, int par){ int sz = 1; for(int ch : G[pos]){ if(ch == par) continue; sz += get_subtree_size(ch, pos); } return subtree_size[pos] = sz; } void make_path(int pos, int par, int set_id){ set_index[pos] = set_id; ele_index[pos] = S[set_id].element.size()-1; int largest_child = -1; int value = 0; for(int ch : G[pos]){ if(ch == par) continue; if(value < subtree_size[ch]){ value = subtree_size[ch]; largest_child = ch; } } for(int ch : G[pos]){ if(ch == par) continue; if(largest_child == ch){ S[set_id].element.push_back(ch); make_path(ch, pos, set_id); }else{ S.emplace_back( ch, S[set_id].depth+1, pos ); make_path(ch, pos, S.size()-1); } } } void init(int root){ subtree_size.resize(G.size(), 0); get_subtree_size(root,root); set_index.resize(G.size(), 0); ele_index.resize(G.size(), 0); S.emplace_back( root,0,root ); make_path( root, root, 0 ); subtree_size.clear(); } public: HeavyLightDecomposition(vector>& G_, int root = 0) : G(G_){ init(root); } //set_index, element_index //S[set_index].element[element_index] == v pair get_position(int v){ return {set_index[v], ele_index[v]}; } }; //Lowest Common Ancestor with HL-decomposition tree //O(log n) / query int LCA(HeavyLightDecomposition& T, int u, int v){ auto pu = T.get_position(u); auto pv = T.get_position(v); if(pu.first == pv.first){ return pu.second < pv.second ? u : v; } if(T.S[pu.first].depth > T.S[pv.first].depth){ swap(pu, pv); swap(u,v); } while(T.S[pu.first].depth != T.S[pv.first].depth){ v = T.S[pv.first].parent_vertex; pv = T.get_position( v ); } while(pu.first != pv.first){ u = T.S[pu.first].parent_vertex; v = T.S[pv.first].parent_vertex; pu = T.get_position(u); pv = T.get_position(v); if(T.S[pv.first].depth == 0) break; if(T.S[pv.first].depth == 0) break; } if(pu.first == pv.first){ return pu.second < pv.second ? u : v; }else{ abort(); } return -1; } int main(){ int n; cin >> n; vector> G(n); for(int i=0; i> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } HeavyLightDecomposition t(G, 0); vector> seg; seg.reserve( t.S.size() ); for(int i=0; i> q; while(q--){ int u,v; cin >> u >> v; u--; v--; int p = LCA(t, u,v); while( t.get_position(u).first != t.get_position(p).first ){ auto tmp = t.get_position(u); seg[ tmp.first ].range_add(0, tmp.second+1, 1); ans += seg[ tmp.first ].get_range_value(0, tmp.second+1); u = t.S[ tmp.first ].parent_vertex; } while( t.get_position(v).first != t.get_position(p).first ){ auto tmp = t.get_position(v); seg[ tmp.first ].range_add(0, tmp.second+1, 1); ans += seg[ tmp.first ].get_range_value(0, tmp.second+1); v = t.S[ tmp.first ].parent_vertex; } auto tmp_u = t.get_position(u); auto tmp_v = t.get_position(v); seg[tmp_u.first].range_add( min(tmp_u.second, tmp_v.second), max(tmp_u.second, tmp_v.second)+1, 1); ans += seg[tmp_u.first].get_range_value( min(tmp_u.second, tmp_v.second), max(tmp_u.second, tmp_v.second)+1 ); } cout << ans << endl; return 0; }