#define NDEBUG #include #include #include #include #include template class lazy_st_trees { public: using value_structure = ValueSemigroup; using value_type = typename value_structure::value_type; using operator_structure = OperatorMonoid; using operator_type = typename operator_structure::value_type; using modifier = Modifier; private: class node_type { public: node_type *left, *right, *parent; typename lazy_st_trees::value_type value, sum; typename lazy_st_trees::operator_type lazy; bool reversed; // reverse->lazy template node_type(V &&v) : left(nullptr), right(nullptr), parent(nullptr), value(::std::forward(v)), sum(value), lazy(operator_structure::identity()), reversed(0) {} }; using container_type = ::std::vector; public: using size_type = typename container_type::size_type; private: using pointer = node_type *; using const_pointer = const node_type *; static void reverse(const pointer ptr) { if (ptr) { ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy)); ptr->reversed ^= 1; } } static void act(const pointer ptr, const operator_type &value) { if (ptr) ptr->lazy = operator_structure::operation(::std::move(ptr->lazy), value); } static void push(const pointer ptr) { if (ptr->reversed) { ptr->reversed = 0; ptr->value = value_structure::reverse(::std::move(ptr->value)); ::std::swap(ptr->left, ptr->right); reverse(ptr->left); reverse(ptr->right); } act(ptr->left, ptr->lazy); act(ptr->right, ptr->lazy); ptr->value = modifier::operation(::std::move(ptr->value), ::std::move(ptr->lazy)); ptr->lazy = operator_structure::identity(); } static void propagate(pointer ptr) { pointer prev = nullptr; while (ptr) { ::std::swap(ptr->parent, prev); ::std::swap(ptr, prev); } while (prev) { push(prev); ::std::swap(prev->parent, ptr); ::std::swap(prev, ptr); } } static value_type reflect(const const_pointer ptr) { return modifier::operation( ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum, ptr->lazy); } static void calc(const pointer ptr) { if (ptr->left) { if (ptr->right) ptr->sum = value_structure::operation( value_structure::operation(reflect(ptr->left), ptr->value), reflect(ptr->right)); else ptr->sum = value_structure::operation(reflect(ptr->left), ptr->value); } else { if (ptr->right) ptr->sum = value_structure::operation(ptr->value, reflect(ptr->right)); else ptr->sum = ptr->value; } } static void rotate_l(const pointer ptr, const pointer ch) { ptr->right = ch->left; if (ch->left) ch->left->parent = ptr; calc(ptr); ch->left = ptr; ptr->parent = ch; } static void rotate_r(const pointer ptr, const pointer ch) { ptr->left = ch->right; if (ch->right) ch->right->parent = ptr; calc(ptr); ch->right = ptr; ptr->parent = ch; } static void splay(const pointer ptr) { for (pointer x, y = ptr;;) { x = ptr->parent; if (!x) { return; } else if (x->left == y) { y = x->parent; if (!y) return ptr->parent = nullptr, rotate_r(x, ptr); else if (y->left == x) ptr->parent = y->parent, rotate_r(y, x), rotate_r(x, ptr); else if (y->right == x) ptr->parent = y->parent, rotate_l(y, ptr), rotate_r(x, ptr); else return ptr->parent = y, rotate_r(x, ptr); } else if (x->right == y) { y = x->parent; if (!y) return ptr->parent = y, rotate_l(x, ptr); if (y->right == x) ptr->parent = y->parent, rotate_l(y, x), rotate_l(x, ptr); else if (y->left == x) ptr->parent = y->parent, rotate_r(y, ptr), rotate_l(x, ptr); else return ptr->parent = y, rotate_l(x, ptr); } else { return; } } } static void expose(const pointer ptr) { propagate(ptr); pointer x = ptr, prev = nullptr; while (x) { splay(x); x->right = prev; calc(x); prev = x; x = x->parent; } splay(ptr); calc(ptr); } static void reroot(const pointer ptr) { expose(ptr); reverse(ptr); } container_type nodes; pointer get_ptr(const size_type v) { return nodes.data() + v; } public: lazy_st_trees() : nodes() {} template lazy_st_trees(InputIterator first, InputIterator last) : nodes(first, last) {} bool empty() const { return nodes.empty(); } size_type size() const { return nodes.size(); } bool connected(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); expose(get_ptr(v)); expose(get_ptr(u)); return nodes[v].parent || v == u; } value_type fold_path(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); return nodes[u].sum; } void link(const size_type parent, const size_type child) { assert(parent < size()); assert(child < size()); assert(!connected(parent, child)); reroot(get_ptr(child)); nodes[child].parent = get_ptr(parent); } void cut(const size_type v) { assert(v < size()); expose(get_ptr(v)); nodes[v].left->parent = nullptr; nodes[v].left = nullptr; nodes[v].sum = nodes[v].value; } void update_path(const size_type v, const size_type u, const operator_type &value) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); nodes[u].lazy = value; } template void update_vertex(const size_type v, const F &f) { assert(v < size()); expose(get_ptr(v)); nodes[v].value = f(::std::move(nodes[v].value)); calc(get_ptr(v)); } }; #include #include template class sum_monoid { public: using size_type = Size; using value_type = ::std::pair; static T get(const value_type &x) { return x.first; } static value_type operation(const value_type &x, const value_type &y) { return value_type(x.first + y.first, x.second + y.second); } static value_type identity() { return value_type(T(0), size_type(0)); } static value_type reverse(const value_type &x) { return x; } }; template class plus_monoid { public: using value_type = T; static value_type operation(const value_type &x, const value_type &y) { return x + y; } static value_type identity() { return value_type(0); } static value_type reverse(const value_type &x) { return x; } }; template class sum_plus { public: static ::std::pair operation(const ::std::pair &x, const T &y) { return ::std::pair(x.first + y * x.second, x.second); } }; #include using u32 = unsigned int; void scan(u32 &d) { d = 0; int c; while (c = fgetc(stdin), c == '\n' || c == ' '); do d = d * 10 + c - '0'; while (c = fgetc(stdin), c != '\n' && c != ' '); } int main() { using u64 = unsigned long long; using tp = sum_monoid::value_type; u32 n; scan(n); ::std::vector a(n, { 1,1 }); lazy_st_trees, plus_monoid, sum_plus> st(a.begin(),a.end()); for (int i = 0;i < n;++i) st.update_vertex(i, [](tp) {return tp(1, 1);}); u32 u, v; while (--n) { scan(u); scan(v); st.link(u - 1, v - 1); } scan(n); u64 ans = 0; while (n--) { scan(u); scan(v); ans += st.fold_path(u - 1, v - 1).first; st.update_path(u - 1, v - 1, 1); } printf("%llu\n", ans); return 0; }