解题思路

　　对于一段区间考虑每条边的贡献，即\(ans=\sum\limits_{i=l}^{r-1}(i-l+1)*(r-i)*w(i)\)，把这个暴力展开，得到一个关于\(i\)的多项式，然后发现只需要维护\(\sum a(i)\)，\(\sum a(i)*i\)和\(\sum a(i)*i^2\)，线段树维护即可。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define int long longusing namespace std;const int N=100005;typedef long long LL;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;LL sum0[N<<2],sum1[N<<2],sum2[N<<2];LL tag0[N<<2],tag1[N<<2],tag2[N<<2];LL a1[N],a2[N];inline void pushdown(int x,int l,int r){    int mid=(l+r)>>1;    if(tag0[x]){        sum0[x<<1]+=tag0[x]*(mid-l+1);        sum0[x<<1|1]+=tag0[x]*(r-mid);        tag0[x<<1]+=tag0[x]; tag0[x<<1|1]+=tag0[x];        tag0[x]=0;    }    if(tag1[x]){        sum1[x<<1]+=tag1[x]*(a1[mid]-a1[l-1]);        sum1[x<<1|1]+=tag1[x]*(a1[r]-a1[mid]);        tag1[x<<1]+=tag1[x]; tag1[x<<1|1]+=tag1[x];        tag1[x]=0;    }    if(tag2[x]){        sum2[x<<1]+=tag2[x]*(a2[mid]-a2[l-1]);        sum2[x<<1|1]+=tag2[x]*(a2[r]-a2[mid]);        tag2[x<<1]+=tag2[x]; tag2[x<<1|1]+=tag2[x];        tag2[x]=0;    }}void update(int x,int l,int r,int L,int R,int k){    if(L<=l && r<=R) {        sum0[x]+=(r-l+1)*k; tag0[x]+=k;        sum1[x]+=(LL)(a1[r]-a1[l-1])*k; tag1[x]+=k;        sum2[x]+=(LL)(a2[r]-a2[l-1])*k; tag2[x]+=k;        return ;    }    int mid=(l+r)>>1;pushdown(x,l,r);    if(L<=mid) update(x<<1,l,mid,L,R,k);    if(mid
         
          >1; LL ret=0; pushdown(x,l,r); if(L<=mid) ret+=query0(x<<1,l,mid,L,R); if(mid
          
           >1; LL ret=0; pushdown(x,l,r); if(L<=mid) ret+=query1(x<<1,l,mid,L,R); if(mid
           
            >1; LL ret=0; pushdown(x,l,r); if(L<=mid) ret+=query2(x<<1,l,mid,L,R); if(mid