#include using namespace std; typedef long long LL; typedef vector V; typedef vector Graph; struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init; //heavy light decomposition namespace hld{ #define SZ 120000 int mem[5][SZ]; }; class HLD{ private: int *treesize; Graph *tree; public: int size,*group,*id,*par,*bg; private: void setTreeSize(int v){ treesize[v]=1; for(auto &u:(*tree)[v]){ setTreeSize(u); treesize[v]+=treesize[u]; } } void build(int v,int g,int& i){ group[v]=g; id[v]=i++; Graph &gr=(*tree); const int sz=gr[v].size(); if(sz){ int h=gr[v][0]; for(auto &u:gr[v]) if(treesize[h]; vector

decomposition(int r,int c){ vector

res; while(group[c]!=group[r]){ res.push_back(P(bg[group[c]],id[c])); c=par[group[c]]; } res.push_back(P(id[r],id[c])); return res; } }; void make_tree(int v,Graph& G,V& Par,V& D, Graph& C){ for(auto &e:G[v]){ if(e!=Par[v]){ C[v].push_back(e); D[e]=D[v]+1; Par[e]=v; make_tree(e,G,Par,D,C); } } } //lcaの準備 void build_PP(V& P,vector& PP){ int N = P.size(); for(int i = 0; i < N; i++)PP[0][i] = P[i]; for(int k = 0,f=1;f; k++){ f=0; for(int i = 0; i < N; i++){ if(PP[k][i]<0)PP[k+1][i]=-1; else {PP[k+1][i]=PP[k][PP[k][i]];f=1;} } } } int lca(int u,int v,V& D,vector &PP){ if(D[u] > D[v])swap(u,v); for(int k = 0,d;(d=D[v]-D[u]); k++)if((d >> k) & 1)v=PP[k][v]; if(u==v)return v; for(int k = PP.size() - 1; k >=0 ; k--){ if(PP[k][u]!=PP[k][v]){ u=PP[k][u]; v=PP[k][v]; } } return PP[0][u]; } #define SIZE 1000000 #define L(v) (v*2+1) #define R(v) (v*2+2) #define SET 0 #define ADD 1 #define GET 2 typedef LL val; struct node{ int bg,ed; val v,add; inline val getval(){ return v+(1+ed-bg)*add; } inline void init(int b,int e){ bg =b,ed=e; v=0,add=0; } bool isleaf(){return bg==ed;} }mem[SIZE]; inline val comb(val l,val r){ return l+r; } class segTree{ private: node *t; void make_tree(int bg,int ed,int v=0){ node *p=t+v; p->init(bg,ed); if(!p->isleaf()){ int m=(bg+ed)/2; make_tree(bg,m,L(v)); make_tree(m+1,ed,R(v)); } } public: using P=pair; segTree(int bg,int ed):t(mem){make_tree(bg,ed);} inline void lazy_update(int v){ node *p=t+v,*l=t+L(v),*r=t+R(v); if(p->isleaf())return; l->add+=p->add; r->add+=p->add; p->add=0; } inline void update(int v){ node *p=t+v,*l=t+L(v),*r=t+R(v); if(p->isleaf()){ p->v+=p->add; p->add=0; } else{ p->v=comb(l->getval(),r->getval()); } } val treat(int type,int bg,int ed,val x,int v=0){ node *p=t+v,*l=t+L(v),*r=t+R(v); lazy_update(v); if(P(bg,ed)==P(p->bg,p->ed)){ if(type==ADD)p->add+=x; update(v); return p->getval(); } int m; val res=0; if(bg<=(m=min(ed,l->ed))) res=comb(res,treat(type,bg,m,x,L(v))); if((m=max(bg,r->bg))<=ed) res=comb(res,treat(type,m,ed,x,R(v))); update(v); return res; } val get(int bg,int ed){ return treat(GET,bg,ed,val()); } val add(int bg,int ed,val x){ // cout<<"add:"<>N; Graph g(N+1),child(N+1); V depth(N+1,0),par(N+1,-1); vector parpar(20,V(N+1,-1)); g[0].push_back(1); for(int i=1;i>u>>v; g[u].push_back(v); g[v].push_back(u); } make_tree(0,g,par,depth,child); build_PP(par,parpar); HLD h(&child); segTree st(0,N); int Q; LL res=0; cin>>Q; while(Q--){ int a,b; cin>>a>>b; int ca=lca(a,b,depth,parpar); LL ans=0; //cout<<"(a,b,ca)="<