Idea

$$\sum_{i=1}^r (dep_u+dep_i-2\times dep_{lca})=\sum_{i=1}^r dep_i+dep_u\times r+\sum dep_{lca}$$

Code

#include <bits/stdc++.h>
#define N 200010
#define inf INT_MAX
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
int son[N],fa[N],siz[N],top[N],fv[N],num[N];
ll sdep[N],dep[N],lastans;
ll x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
struct Mon{
int age,id;
Mon(int a=0,int b=0){
age=a,id=b;
}
bool operator < (const Mon &x) const{
return age<x.age;
}
}mon[N];
struct Node{
int ls,rs,lazy;
ll sum,esum;
}t[N<<7];
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[N<<1];
}
void Pre_Work(int u,int f){
fa[u]=f,siz[u]=1;
int mx=-1;
int v=l[i].to;if (v==f) continue;
dep[v]=dep[u]+l[i].val;fv[v]=l[i].val;
Pre_Work(v,u);siz[u]+=siz[v];
if (siz[v]>mx) mx=siz[v],son[u]=v;
}
}
void Re_Build(int u,int topf){
top[u]=topf,id[u]=++cnt;num[cnt]=fv[u];
if (son[u]) Re_Build(son[u],topf);
int v=l[i].to;
if (v!=son[u]&&v!=fa[u])
Re_Build(v,v);
}
}
void Build(int &p,int l,int r){
int pre=p;p=++cnt;t[p]=t[pre];
if (l==r) {t[p].esum=num[l];return;}
Build(t[p].ls,l,mid);
Build(t[p].rs,mid+1,r);
t[p].esum=t[t[p].ls].esum+t[t[p].rs].esum;
}
void Update(int &p,int l,int r,int L,int R){
int pre=p;p=++cnt;t[p]=t[pre];
if (L<=l&&r<=R){
++t[p].lazy;
t[p].sum+=t[p].esum;
return;
}
if (mid>=L) Update(t[p].ls,l,mid,L,R);
if (mid<R) Update(t[p].rs,mid+1,r,L,R);
t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum+t[p].esum*t[p].lazy;
}
ll Query(int p,int l,int r,int L,int R,int add){
}
ll Path_Query(int u,int ver){
ll res=0;
while(top[u]!=1){
res+=Query(rt[ver],1,n,id[top[u]],id[u],0);
u=fa[top[u]];
}
res+=Query(rt[ver],1,n,1,id[u],0);
return res;
}
void Path_Update(int u,int ver){
while(top[u]!=1){
Update(rt[ver],1,n,id[top[u]],id[u]);
u=fa[top[u]];
}
Update(rt[ver],1,n,1,id[u]);
}
ll Solve(int u,int ver){
return sdep[ver]+dep[u]*ver-2*Path_Query(u,ver);
}
int main(){
for (int i=1;i<=n;++i)
for (int i=2,a,b,c;i<=n;++i)
Pre_Work(1,0);Re_Build(1,1);cnt=0;
sort(mon+1,mon+1+n);
Build(rt[0],1,n);
for (int i=1;i<=n;++i)
sdep[i]=sdep[i-1]+dep[mon[i].id],
rt[i]=rt[i-1],Path_Update(mon[i].id,i);
for (int i=1;i<=q;++i){
int u;
ll l,r;
}