在很久很久以前，有一棵n个点的树，每个点有一个点权。

现在有q次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。

参考：洛谷树剖题解（%%rqy，zzq）

正解是动态点分治，然而：

1.难写，（对于我来说）也不会写。

2.第一个想到的难道不应该是树剖吗……

于是果断采用树剖，简易想法就是维护每个结点的子树权值和\(s\)和权值和的平方\(s^2\)。

先思考对于一个每次询问只询问1为根的询问。

我们把修改操作改为对节点\(u\)权值\(+x\)，实际上只对\(1-u\)路径上的点的\(s^2\)有影响。

设\(i\)为\(1-u\)路径上的点，则这部分修改对答案的贡献为：

\(\sum_i(s_i+v)^2-\sum_is_i^2\)

\(=\sum_i(2*s_i*v+v*v)\)

现在考虑换根为\(u\)操作+修改，实际上还是只对\(1-u\)路径上的点的\(s^2\)有影响。

设\(ans\)为以1为根的答案，\(a\)数组为以1为根的\(s\)，\(b\)数组为以\(u\)为根的\(s\)，将\(1-u\)路径上的点按顺序编号为\(1-k\)。

不难得出\(a_{i+1}+b_i=a _1=b_k\)

于是答案为：

\(ans-\sum_ia_i^2+\sum_ib_i^2\)

\(=ans-\sum_ia_i^2+\sum_i(a_1-a_{i+1})^2\)

\(=ans+(k-1)*a_1^2-2*a_1*(\sum_ia_i-a_1)\)

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=2e5+5;const int INF=2147483647;inline int read(){    int X=0,w=0;char ch=0;    while(ch<'0'||ch>'9'){w|=ch=='-';ch=getchar();}    while(ch>='0'&&ch<='9')X=(X<<3)+(X<<1)+(ch^48),ch=getchar();    return w?-X:X;}struct node{    int to,nxt;}edge[2*N];int head[N],cnt,tot,n,q;int fa[N],dep[N],size[N],son[N],top[N],pos[N],idx[N],val[N];ll sum[N],sum1[N*4],sum2[N*4],lazy[N*4];inline void add(int u,int v){    edge[++cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt;}void dfs1(int u){    size[u]=1;sum[u]=val[u];    for(int i=head[u];i;i=edge[i].nxt){        int v=edge[i].to;        if(v==fa[u])continue;        fa[v]=u;dep[v]=dep[u]+1;        dfs1(v);        size[u]+=size[v];sum[u]+=sum[v];        if(!son[u]||size[v]>size[son[u]])son[u]=v;    }    return;}void dfs2(int u,int anc){    pos[u]=++tot;    idx[tot]=u;    top[u]=anc;    if(!son[u])return;    dfs2(son[u],anc);    for(int i=head[u];i;i=edge[i].nxt){        int v=edge[i].to;        if(v==fa[u]||v==son[u])continue;        dfs2(v,v);    }    return;}inline void qmfy(int a,int l,int r,int x){    lazy[a]+=x;    sum2[a]+=x*x*(r-l+1)+2*x*sum1[a];    sum1[a]+=x*(r-l+1);}inline void push(int a,int l,int r){    if(!lazy[a])return;    int mid=(l+r)>>1;    qmfy(a*2,l,mid,lazy[a]);    qmfy(a*2+1,mid+1,r,lazy[a]);    lazy[a]=0;}inline void upt(int a){    sum1[a]=sum1[a*2]+sum1[a*2+1];    sum2[a]=sum2[a*2]+sum2[a*2+1];}void build(int a,int l,int r){    if(l==r){        sum1[a]=sum[idx[l]];        sum2[a]=sum1[a]*sum1[a];        return;    }    int mid=(l+r)>>1;    build(a*2,l,mid);    build(a*2+1,mid+1,r);    upt(a);}void modify(int a,int l,int r,int l1,int r1,ll v){    if(r1
        
         
          >1; push(a,l,r); modify(a*2,l,mid,l1,r1,v); modify(a*2+1,mid+1,r,l1,r1,v); upt(a);}void pathmodify(int u,int v,ll c){ while(top[u]!=top[v]){ if(dep[top[u]]
          
           dep[v])swap(u,v); modify(1,1,n,pos[u],pos[v],c); return;}ll query(int a,int l,int r,int l1,int r1){ if(r1
           
            r)return 0; if(l1<=l&&r<=r1)return sum1[a]; int mid=(l+r)>>1; push(a,l,r); return query(a*2,l,mid,l1,r1)+query(a*2+1,mid+1,r,l1,r1);}ll pathquery(int u,int v){ ll res=0; while(top[u]!=top[v]){ if(dep[top[u]]
            
             dep[v])swap(u,v); return res+query(1,1,n,pos[u],pos[v]);}inline ll nodequery(int u){ ll a=query(1,1,n,pos[1],pos[1]); ll ans=sum2[1]; ll b=pathquery(u,1); return ans+(dep[u]-1)*a*a-2*a*(b-a);}inline void init(){ dep[1]=1;dfs1(1);dfs2(1,1);}int main(){ n=read(),q=read(); for(int i=1;i
            
           
          
         
        
       
      
     
    

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：

+++++++++++++++++++++++++++++++++++++++++++