//根付き木にしてLCAしてimos #include #include #include #include #include #include using namespace std; template< typename T, typename F> struct SegmentTree{ private: int n; vector node; F f; T initer; public: SegmentTree(int n_, F f, T initer) : f(f),initer(initer) { n = 1; while(n < n_)n*=2; node.resize(2*n-1, initer); } SegmentTree(int n_, F f,T initer, vector x) : f(f),initer(initer) { n = 1; while(n < n_)n*=2; node.resize(2*n-1, initer); set(x); } void set(vector x){ for(int i = 0; (int)x.size() > i; i++){ update(i,x[i]); } } void update(int x, T val){ x += (n-1); node[x] = val; while(x > 0){ x = (x-1)/2; node[x] = f(node[2*x+1],node[2*x+2]); } } void add(int x, T val){ x += (n-1); node[x] += val; while(x > 0){ x = (x-1)/2; node[x] = f(node[2*x+1],node[2*x+2]); } } T getf(int a,int b, int k=0, int l=0, int r=-1){ if(r < 0){ r = n-1; } if(r < a || b < l){ return initer; } if(a <= l && r <= b){ return node[k]; } T vl = getf(a,b,2*k+1,l,(l+r)/2); T vr = getf(a,b,2*k+2,(l+r)/2+1,r); return f(vl,vr); } }; template SegmentTree get_segment_tree(int N, const F &f, T initer){ return SegmentTree{N,f,initer}; } template SegmentTree get_segment_tree(int N, const F &f, T initer, vector x){ return SegmentTree{N,f,initer,x}; } struct EulerTourForLCA { int n; vector> edge; vector> timeline; vector> stump; vector parent; EulerTourForLCA(int n, vector> edge): n(n), edge(edge), timeline(2*n, {-1, 0}), stump(n, {-1,-1}), parent(n, 0), lock(n, false) {} void build(int top){ timer = 0; lock.assign(n, false); lock[top] = true; dfs(top, 0); } const pair operator[](int index){ return stump[index]; } private: vector lock; int timer = 0; void dfs(int vertex, int depth){ stump[vertex].first = timer; timeline[timer].first = vertex; timeline[timer].second = depth; timer++; for(int i = 0; (int)edge[vertex].size() > i; i++){ if(!lock[edge[vertex][i]]){ lock[edge[vertex][i]] = true; parent[edge[vertex][i]] = vertex; dfs(edge[vertex][i], depth+1); } } stump[vertex].second = timer; timeline[timer].first = parent[vertex]; timeline[timer].second = depth-1; timer++; } }; struct LowestCommonAncestor { int n; vector> edge; EulerTourForLCA et; function(pair, pair)> RMQ = [](pair a, pair b){ if(a.second < b.second)return a; return b; }; //function> RMQ = [](pair a, pair b){ //}; SegmentTree, decltype(RMQ)> st; LowestCommonAncestor(int n, vector> edge):n(n), edge(edge), et(n, edge), st(2*n, RMQ, {n+1, n+1}){ et.build(0); st.set(et.timeline); } int compute(int l, int r){ auto ls = et[l].first; auto rs = et[r].first; if(ls > rs)swap(ls, rs); auto mn = st.getf(ls, rs); return mn.first; } }; using LCA = LowestCommonAncestor; int main(){ int n;cin>>n; vector> A(n); for(int i = 0; n-1 > i; i++){ int u,v;cin>>u>>v; u--;v--; A[u].push_back(v); A[v].push_back(u); } LCA lca(n, A); vector> B(n, {0, 0}); int q;cin>>q; for(int i = 0; q > i; i++){ int a,b;cin>>a>>b;a--;b--; auto z = lca.compute(a,b); B[z].first++; B[a].second++; B[b].second++; cout << z << " " << a << " " << b << endl; } cout << "--" << endl; for(int i = 0; n > i; i++){ cout << B[i].first << " " << B[i].second << endl; } cout << "--" << endl; // get leaf queue X; vector vis(n, 0); X.push(0); vis[0] = -1; vector leaf; while(X.size()){ auto x = X.front(); X.pop(); cout << x << endl; bool found = false; for(int i = 0; A[x].size() > i; i++){ if(vis[A[x][i]])continue; vis[A[x][i]] = -1; X.push(A[x][i]); found = true; } if(!found)leaf.push_back(x); } queue S; vector count(n, 0); for(int i = 0; leaf.size() > i; i++){ S.push(leaf[i]); cout << leaf[i] << endl; count[leaf[i]] = B[leaf[i]].second; vis[leaf[i]] = 2; } for(int i = 0; n > i; i++)cout << count[i] << " "; cout << endl; while(S.size()){ auto x = S.front(); S.pop(); if(vis[x] != 2){ cout << x << endl; count[x] = count[x] + B[x].second - B[x].first; } vis[x] = 1; for(int i = 0; A[x].size() > i; i++){ if(vis[A[x][i]] == 1)continue; if(vis[A[x][i]] == -1){ S.push(A[x][i]); } vis[A[x][i]] = 0; count[A[x][i]] += count[x] - B[x].first; } } long long ans = 0; for(int i = 0; n > i; i++){ ans += count[i]*(count[i]+1)/2; } cout << ans << endl; }