解题思路

树链剖分裸题，线段树维护。

代码

#include
    
     #include
     
      #include
      
       #define int long longusing namespace std;const int MAXN = 100005;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return f?x:-x;}int n,m,a[MAXN],sum[MAXN<<2],lazy[MAXN<<2];int w[MAXN],id[MAXN],fa[MAXN],dep[MAXN],son[MAXN],siz[MAXN],top[MAXN];int num,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1];inline void add(int bg,int ed){    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;}void dfs1(int x,int f,int d){    dep[x]=d,fa[x]=f,siz[x]=1;    int maxson=-1;    for(register int i=head[x];i;i=nxt[i]){        int u=to[i];if(u==f) continue;        dfs1(u,x,d+1);        siz[x]+=siz[u];        if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}    }}void dfs2(int x,int topf){    id[x]=++num,w[num]=a[x],top[x]=topf;    if(!son[x]) return;    dfs2(son[x],topf);    for(register int i=head[x];i;i=nxt[i]){        int u=to[i];if(u==fa[x] || u==son[x]) continue;        dfs2(u,u);    }}//----------------------xds------------------------inline void pushdown(int x,int ln,int rn){    sum[x<<1]+=ln*lazy[x],sum[x<<1|1]+=rn*lazy[x];    lazy[x<<1]+=lazy[x],lazy[x<<1|1]+=lazy[x];    lazy[x]=0;}void build(int x,int l,int r){    if(l==r){        sum[x]=w[l];        return;    }    int mid=l+r>>1;    build(x<<1,l,mid);    build(x<<1|1,mid+1,r);    sum[x]=sum[x<<1]+sum[x<<1|1];}void update(int x,int l,int r,int L,int R,int k){    if(L<=l && r<=R){        sum[x]+=(r-l+1)*k;        lazy[x]+=k;        return;    }    int mid=l+r>>1;    if(lazy[x]) pushdown(x,mid-l+1,r-mid);    if(mid>=L) update(x<<1,l,mid,L,R,k);    if(mid
       
        >1,ret=0;    if(lazy[x]) pushdown(x,mid-l+1,r-mid);    if(mid>=L) ret+=query(x<<1,l,mid,L,R);    if(mid