#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i>to; int root; vectorpar,pathtop,in,out; public: vectorstsize; private: void st_dfs(int x,int p){ par[x]=p; stsize[x]=1; for(auto &i:to[x]){ if(i==p){ if(i==to[x].back())break; else swap(i,to[x].back()); } st_dfs(i,x); stsize[x]+=stsize[i]; if(stsize[i]>stsize[to[x][0]]){ swap(i,to[x][0]); } } } void hld_dfs(int x,int p,int &id){ in[x]=id++; for(auto i:to[x])if(i!=p){ pathtop[i]=(i==to[x][0]?pathtop[x]:i); hld_dfs(i,x,id); } out[x]=id; } public: HeavyLightDecomposition(int n,int root=0):n(n),to(n),stsize(n),par(n),in(n),out(n),root(root),pathtop(n){} void add_edge(int u,int v){ to[u].emplace_back(v); to[v].emplace_back(u); } void build(){ st_dfs(0,-1); pathtop[root]=root; int id=0; hld_dfs(0,-1,id); } inline int get(int x)const{return in[x];} int lca(int u,int v)const{ int pu=pathtop[u],pv=pathtop[v]; while(pathtop[u]!=pathtop[v]){ if(in[pu]>in[pv])u=par[pu],pu=pathtop[u]; else v=par[pv],pv=pathtop[v]; } return (in[u]>in[v]?v:u); } void subtree_query(int u ,const function &f){ f(in[u],out[u]); } void path_query(int u,int v,const function&f){ int pu=pathtop[u],pv=pathtop[v]; while(pathtop[u]!=pathtop[v]){ if(in[u]>in[v])f(in[pu],in[u]+1),u=par[pu],pu=pathtop[u]; else f(in[pv],in[v]+1),v=par[pv],pv=pathtop[v]; } if(in[u]>in[v])swap(u,v); f(in[u],in[v]+1); } }; struct S{ int sz; ll sum; }; S op(S a,S b){ return {a.sz+b.sz,a.sum+b.sum}; } S e(){return {0,0};} S mapping(ll f,S x){ if(f==0)return x; x.sum+=f*x.sz; return x; } ll composition(ll a,ll b){return a+b;} ll id(){return 0;} void SOLVE(){ int n; cin>>n; HeavyLightDecomposition hld(n); rep(i,n-1){ int u,v; cin>>u>>v; u--,v--; hld.add_edge(u,v); } hld.build(); int q; cin>>q; vectorhoge(n,{1,0}); lazy_segtreeseg(hoge); ll ans=0; while(q--){ int u,v; cin>>u>>v; u--,v--; hld.path_query(u,v,[&](int a,int b){seg.apply(a,b,1);}); hld.path_query(u,v,[&](int a,int b){ans+=seg.prod(a,b).sum;}); debug(ans); } cout<