#include using namespace std; typedef long long ll; #define PB push_back struct SEG{ ll seg[1<<18],la[1<<18]; SEG(void){ for(int i=0;i<1<<18;i++){ seg[i]=0; la[i]=0; } } void lazy(ll l,ll r,int k){ if(la[k]!=0){ seg[k]+=(r-l+1)*la[k]; if(l!=r){ la[k*2+1]+=la[k]; la[k*2+2]+=la[k]; } la[k]=0; } } void add(int a,int b,int l,int r,int k,ll x){ if(rg[100005]; void dfs1(int v,int p){ sz[v]=1; for(int i=0;isz[g[v][0]])swap(g[v][i],g[v][0]); } } } void dfs2(int v,int p,int d,int h){ vs[k]=v; id[v]=k; hd[k]=h; cn[k]=cn[h]; dp[k]=d; k++; for(int i=0;ib)swap(a,b); ans+=seg.sum(a,b,0,(1<<17)-1,0); seg.add(a,b,0,(1<<17)-1,0,1); } printf("%lld\n",ans); }