#include using namespace std; #include /*//-------------------------------------------------------- 木に対して重軽分解をする構造体 refer: https://info.atcoder.jp/entry/algorithm_lectures/heavy_light_decomposition https://nachiavivias.github.io/cp-library/cpp/tree/heavy-light-decomposition.html *///-------------------------------------------------------- struct HeavyLightDecomposition{ private: int N; std::vector par; std::vector dep; std::vector siz; std::vector vertex; std::vector id; std::vector head; public: // G is tree that represented by AdjacencyList HeavyLightDecomposition(std::vector> G,int root=0){ N=std::ssize(G); par.assign(N,-1); dep.assign(N,-1); siz.assign(N,0); vertex.assign(N,-1); id.assign(N,-1); head.assign(N,-1); { // calculate subtree size, put the heave child first in G. auto dfs=[&](auto &dfs, int v, int p=-1) -> void { par[v]=p; dep[v]=(p==-1 ? 0 : dep[p]+1); siz[v]=1; if(!G[v].empty() and G[v][0]==p) std::swap(G[v][0],G[v].back()); for(int &w:G[v]){ if(w==p) continue; dfs(dfs,w,v); siz[v]+=siz[w]; if(siz[w]>siz[G[v][0]]) std::swap(G[v][0],w); } }; dfs(dfs,root); } { int idx=0; auto dfs=[&](auto &dfs,int v,int p=-1) -> void { id[v]=idx; vertex[idx++]=v; for(int &w:G[v]){ if(w==p) continue; bool heavy=(w==G[v][0]); head[w]=(heavy?head[v]:w); dfs(dfs,w,v); } }; head[root]=root; dfs(dfs,root); } } int numVertices() const { return N; } // 頂点vの深さ (dep) int depth(int v) const { return dep[v]; } // 頂点vがHLD配列上で何番目か (id) int toSeq(int v) const { return id[v]; } // HLD配列[seqidx]の頂点番号 (vertex) int toVertex(int seqidx) const { return vertex[seqidx]; } // 頂点vの親 (根なら-1) int parent(int v) const { return par[v]; } // 頂点vのheavyRoot (heavyPathに乗っていなければ自身の番号を返す) int heavyR(int v) const { return head[v]; } // 頂点vのheaveChild 存在しなければ-1 int heavyC(int v) const { if(toSeq(v)==N-1) return -1; int cand=toVertex(toSeq(v)+1); if(same(v,cand)) return cand; return -1; } // 頂点uと頂点vが同一のheavyPathに乗っているか bool same(int u,int v) const { return head[u]==head[v]; } // 頂点uと頂点vについてHLD配列上でuid[v]) swap(u,v); } // 頂点vがheavyPath上で何番目の頂点か int distToHR(int v) const { return id[v]-id[head[v]]; } // 頂点vが含まれるheavyPathを配列で返す stopV=trueでvで止まる // O(len(heavyPath)) std::vector heavyPath(int v,bool stopV=false) const { std::vector path; int idx=id[head[v]]; while(idx!=-1){ path.emplace_back(idx); if(stopV and idx==v) break; idx=heavyC(idx); } return path; } // Level Ancestor 頂点vの祖先であって深さdにある頂点番号を返す // O(logN) int LA(int v,int d) const { assert(dep[v]>=d); while(dep[head[v]]>d){ v=par[head[v]]; } return vertex[id[v]-(dep[v]-d)]; } // Lowest Common Ancestor 頂点u,vの最近共通祖先なる頂点番号を返す // O(logN) int LCA(int u,int v) const { while(!same(u,v)){ if(id[u]>id[v]) std::swap(u,v); v=par[head[v]]; } return (id[u] < id[v] ? u:v); } // 任意の2頂点u,vの距離を返す O(logN) int dist(int u,int v) const { const int w=LCA(u,v); return (dep[u]-dep[w])+(dep[v]-dep[w]); } // Jump on Tree 2頂点s,t及び非負整数iについて、 // パスstにおけるi番目の頂点番号を返す O(logN) int jump(int u,int v,int i) const { const int w=LCA(u,v); const int d=(dep[u]-dep[w])+(dep[v]-dep[w]); if(dios::sync_with_stdio(false); int N; cin>>N; vector G(N,vector()); for(int i=0;i>u>>v; u--,v--; G[u].emplace_back(v); G[v].emplace_back(u); } HeavyLightDecomposition HLD(G); struct node1{ long val,len; }; auto op1=[](node1 a,node1 b){ return node1(a.val+b.val,a.len+b.len); }; auto e1=[]{ return node1(0l,0l); }; auto mapping1=[](long f,node1 x){ return node1(x.val+x.len*f,x.len); }; auto composition1=[](long f,long g){ return f+g; }; auto id1=[]{ return 0l; }; vector ini1(N,node1(0,1)); atcoder::lazy_segtree seg(ini1); int Q; cin>>Q; // vector cnt(N); // for(int i=0;i>a>>b; a--,b--; // bool found=false; // auto dfs=[&](this auto dfs,int p,int par=-1) -> void { // if(p==b){ // found=true; // cnt[HLD.toSeq(p)]++; // return; // } // for(auto q:G[p]) if(q!=par){ // dfs(q,p); // if(found){ cnt[HLD.toSeq(p)]++; break; } // } // if(p==a) found=false; // }; // dfs(a); while(!HLD.same(a,b)){ HLD.normalizePair(a,b); const int r=HLD.heavyR(b); seg.apply(HLD.toSeq(r),HLD.toSeq(b)+1,1); b=HLD.parent(r); // cout<