#include using namespace std; #define ll long long #define rep(i, n) for (int i = 0; i < (int)(n); i++) template bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} const long long mod=998244353; const long long mod2=469762049; const long long mod100=1000000007; struct HLD{ //0-indexed //根が0の根付き木で実装 vectorV;//入りがけ順 vectorid;//頂点iがどこにあるか vectorhead;//頂点iが属するheavy pathの親 vectorchild;//頂点iが属するheavy pathの子 vector>G;//グラフ vectorsubtree;//部分木サイズ vectorparent; //初期化 HLD(int N){ id.assign(N,-1); head.assign(N,-1); child.assign(N,-1); subtree.assign(N,-1); parent.assign(N,-1); G.assign(N,{}); } //辺の追加 void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } //テーブルの作成。辺を追加した後にやる void make_table(){ auto dfs1=[&](auto &dfs1,int pos,int last)->void { subtree[pos]=1; for(auto nex:G[pos]){ if(nex==last) continue; parent[nex]=pos; dfs1(dfs1,nex,pos); subtree[pos]+=subtree[nex]; } return; }; dfs1(dfs1,0,-1); auto dfs2=[&](auto &dfs2,int pos,int last,int h)->int { id[pos]=(int)V.size(); V.push_back(pos); head[pos]=h; pairpriority={-1,-1}; for(auto nex:G[pos]){ if(nex==last) continue; chmax(priority,{subtree[nex],nex}); } if(priority.second==-1){ child[pos]=pos; return pos; } child[pos]=dfs2(dfs2,priority.second,pos,h); for(auto nex:G[pos]){ if(nex==last) continue; if(priority.second==nex) continue; dfs2(dfs2,nex,pos,nex); } return child[pos]; }; dfs2(dfs2,0,-1,0); return; } int LCA(int u,int v){ while(true){ if(head[u]==head[v]){ if(id[u]>id[v]) return v; else return u; } if(id[u]>id[v]){ u=parent[head[u]]; } else{ v=parent[head[v]]; } } } }; template struct lazysegtree{ using F1=function; using F2=function; using F3=function; vectornode; vectorlazy; int N;int log;F1 op;T e;F2 mapping;F3 composition;F id; lazysegtree(int n,F1 op,T e,F2 mapping,F3 composition,F id) :op(op),e(e),mapping(mapping),composition(composition),id(id){ N=1; log=1; while(N=0;i--){ lazy[pos*2]=composition(lazy[pos*2],lazy[pos]); lazy[pos*2+1]=composition(lazy[pos*2+1],lazy[pos]); node[pos*2]=mapping(node[pos*2],lazy[pos]); node[pos*2+1]=mapping(node[pos*2+1],lazy[pos]); lazy[pos]=id; pos<<=1; if((p>>i)&1) pos++; } lazy[pos]=id; node[pos]=x; while(pos>=2){ pos/=2; node[pos]=op(node[pos*2],node[pos*2+1]); } return; } void apply(int l,int r,int a,int b,int u,F f){ if(b<=l || r<=a) return; if(l<=a && b<=r){ lazy[u]=composition(lazy[u],f); node[u]=mapping(node[u],f); return; } lazy[u*2]=composition(lazy[u*2],lazy[u]); lazy[u*2+1]=composition(lazy[u*2+1],lazy[u]); node[u*2]=mapping(node[u*2],lazy[u]); node[u*2+1]=mapping(node[u*2+1],lazy[u]); lazy[u]=id; int m=(a+b)/2; apply(l,r,a,m,u*2,f); apply(l,r,m,b,u*2+1,f); node[u]=op(node[u*2],node[u*2+1]); return; } void apply(int l,int r,F f){//[l,r)を変更 l++;r++; apply(l,r,1,N+1,1,f); } void apply(int p,F f){ apply(p,p+1,1,N+1,1,f); } T fold(int l,int r,int a,int b,int u){ if(b<=l || r<=a)return e; if(l<=a && b<=r){ return node[u]; } int m=(a+b)/2; T L=mapping(fold(l,r,a,m,u*2),lazy[u]); T R=mapping(fold(l,r,m,b,u*2+1),lazy[u]); return op(L,R); } T fold(int l,int r){//[l,r)をを求める l++;r++; return fold(l,r,1,N+1,1); } T fold(int p){ p++; return fold(p,p+1,1,N+1,1); } }; struct S{ ll siz,ans; }; S e(){ S res; res.siz=0; res.ans=0; return res; } S op(S a,S b){ S res; res.siz=a.siz+b.siz; res.ans=a.ans+b.ans; return res; } S mapping(S x,ll f){ x.ans+=f*x.siz; return x; } ll composition(ll f,ll g){ return f+g; } int main(){ cout.tie()->sync_with_stdio(0); cin.tie(0); int N;cin>>N; int u[N-1],v[N-1]; for(int i=0;i>u[i]>>v[i]; u[i]--;v[i]--; } int Q;cin>>Q; int A[Q],B[Q]; for(int i=0;i>A[i]>>B[i]; A[i]--;B[i]--; } HLD H(N); for(int i=0;iseg(N,op,e(),mapping,composition,0LL); for(int i=0;i