#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const int MAXN=100010; vector> g; int sz[MAXN], par[MAXN]; bool isremoved[MAXN]; vector centroids; int dist[MAXN]; void findcentroid_rec(int x, int p, int size, vector

&v){ sz[x]=1, par[x]=p; v.push_back({x, dist[x]}); bool cent=1; for(auto y:g[x]){ if(y==p) continue; if(isremoved[y]) continue; dist[y]=dist[x]+1; findcentroid_rec(y, x, size, v); if(sz[y]>size/2) cent=0; sz[x]+=sz[y]; } if(size-sz[x]>size/2) cent=0; if(cent) centroids.push_back(x); } pair>> findcentroid(int root, int size, vector

&v){ vector> subtrees; centroids.clear(); findcentroid_rec(root, -1, size, v); int cent=centroids[0]; for(auto y:g[cent]){ if(isremoved[y]) continue; if(y==par[cent]){ subtrees.push_back({y, size-sz[cent]}); }else{ subtrees.push_back({y, sz[y]}); } } return make_pair(cent, subtrees); } int parc[MAXN]; vector

vd[MAXN], vdc[MAXN]; void dfs(int x, int p, int cent){ vd[cent].push_back({x, dist[x]}); for(auto y:g[x]){ if(y==p) continue; if(isremoved[y]) continue; dist[y]=dist[x]+1; dfs(y, x, cent); } } void myon(int root, int size, int p=-1){ if(size<=1){ parc[root]=p; vdc[root].push_back({root, 0}); vd[root].push_back({root, 0}); return; } dist[root]=0; vector

v; auto pr=findcentroid(root, size, v); int cent=pr.first; swap(vdc[cent], v); dist[cent]=0; dfs(cent, -1, cent); parc[cent]=p; isremoved[cent]=1; for(auto prr:pr.second){ if(!isremoved[prr.first]){ myon(prr.first, prr.second, cent); } } } struct LCA{ vector> g; vector d; vector> p; int log; int n; LCA(const vector> &g):g(g), d(g.size()), n(g.size()){ log=0; while(1<(n)); } void dfs(int x, int prev){ for(auto y:g[x]){ if(y==prev) continue; d[y]=d[x]+1; p[0][y]=x; dfs(y, x); } } void build(){ dfs(0, -1); for(int i=1; id[b]) swap(a, b); int dd=d[b]-d[a], i=0; int a1=a, b1=b; while(dd){ if(dd&1) b1=p[i][b1]; dd>>=1; i++; } if(a1==b1) return a1; for(int j=log-1; j>=0; j--){ if(p[j][a1]!=p[j][b1]){ a1=p[j][a1], b1=p[j][b1]; } } return p[0][a1]; } int dist(int a, int b){ return d[a]+d[b]-2*d[lca(a, b)]; } }; template struct BIT{ vector bit; int size; BIT(){} BIT(int n):size(n), bit(n+1, 0){} void init(int n){ size=n; bit.resize(n+1); } T sum(int i){ //[0, i) T s=0; while(i>0){ s+=bit[i]; i-=(i&(-i)); } return s; } T sum(int l, int r){ //[l, r) return sum(r)-sum(l); } void add(int i, T x){ i++; while(i<=size){ bit[i]+=x; i+=(i&(-i)); } } }; template struct RangeAddPointGet{ BIT bit; RangeAddPointGet(){} RangeAddPointGet(int n):bit(n){} void init(int n){ bit.init(n); } void add(int l, int r, T x){ bit.add(l, x); bit.add(r, -x); } T get(int i){ return bit.sum(i+1); } }; int main() { int n, q; cin>>n>>q; g.resize(n); for(int i=0; i> seg(n), segc(n); for(int i=0; i