#if __has_include() #include #else #include #include #endif using namespace atcoder; using namespace std; using ll=long long; using ld=long double; using P = pair; using TUP = tuple; #define rep(i,n) for (int i = 0; i < (n); ++i) #define drep(i,n) for (int i = (n-1); i >= 0; --i) templateinline bool chmax(t&a,u b){return ainline bool chmin(t&a,u b){return a>b?a=b,1:0;} inline int yn(bool b){cout<<(b?"Yes\n":"No\n");return 0;} const vector di={1,0,-1,0},dj={0,1,0,-1}; using mint = modint998244353; inline ostream&operator<<(ostream&os,const mint& x){os<ostream&operator<<(ostream&os,const vector&x){for(t i:x)os<ostream&operator<<(ostream&os,const vector>&x){for(const vector&i:x)os< vertex,id,head,par,dep; hld(vector> g){ n=g.size(); id.resize(n); head.resize(n); par.resize(n); dep.resize(n); { auto f=[&](auto f,int x,int px)->int{ int cnt=1,mx=0; rep(i,g[x].size()){ int nx=g[x][i]; if(nx==px)continue; int s=f(f,nx,x); cnt+=s; if(chmax(mx,s))swap(g[x][0],g[x][i]); } return cnt; }; f(f,0,0); } { auto f=[&](auto f,int x,int px)->void{ id[x]=vertex.size(); vertex.push_back(x); for(int nx:g[x])if(px!=nx){ par[nx]=x; dep[nx]=dep[x]+1; head[nx]=(nx==g[x][0]?head[x]:nx); f(f,nx,x); } }; f(f,0,0); } } int lca(int u,int v){ while(head[u]!=head[v]){ if(id[u]>id[v])u=par[head[u]]; else v=par[head[v]]; } return id[u]d){ u=par[head[u]]; } return vertex[id[u]-(dep[u]-d)]; } int jump_up(int u,int steps){ return level_ancestor(u,dep[u]-steps); } int jump(int u,int v,int steps){ int c=lca(u,v); int uc=dep[u]-dep[c]; int vc=dep[v]-dep[c]; if(steps < uc)return jump_up(u,steps); else if(steps-uc<=vc)return jump_up(v,uc+vc-steps); else return -1; } template // TODO:可換な演算じゃない場合も成立するようにする void foreach(int u,int v,const F& f,bool on_edge=0){ while(head[u]!=head[v]){ if(id[u]>n; vector> g(n); rep(i,n-1){ int u,v; cin>>u>>v; u--,v--; g[u].push_back(v); g[v].push_back(u); } hld hl(g); ll ans=0; vector v(n,{0,1}); lazy_segtree seg(v); int q; cin>>q; rep(qi,q){ int a,b; cin>>a>>b; a--,b--; hl.foreach(a,b,[&](int l,int r){ seg.apply(l,r,1); ans+=seg.prod(l,r).value; }); } cout<