解题思路：

开始写了个LCT后来发现是错的QAQ

正解是动态点分治。

对于一个点，其答案就是$\sum_{i=1}^{n}sum_{i}^{2}$

很神奇地构造出这个式子$\sum_{i=1}^{n}sum_{i}*(Sum_{tot}-sum_{i})$

其中Sum_tot是一棵树的总权值和。

可以发现它对于一颗树来说是一个定值。

因为它可以理解成一条边两端选点。

将它拆开，就变成了$\sum_{i=1}^{n}{sum_{i}*Sum_{tot}}-\sum_{i=1}^{n}sum_{i}^{2}$

既然整体是定值，不如在根为1的时候构建，然后维护。

然后算前面那个东西就好了。

厉害就厉害在这里，前面那个东西是可以$O(nlog_{2}n)$计算的。

再来构造一次，这个东西将常数项提出去$Sum_{tot}*{\sum_{i=1}^{n}{sum_{i}}}$

显然那个Sum_tot是可以$O(1)$维护的。

后面那个呢？

设当前根为$root$

可以发现对于每一个值产生贡献时在且仅在其父及祖先节点处生效。

所以一共生效了$\mathit{deep_{i}+1}$次

所以说如果设边权为1那么$deep_{i}={\mathit{Dis(i,root)}}$

那么原式就成为了${\sum_{i=1}^{n}{val_{i}}}+{\sum_{i=1}^{n}{\mathit{Dis(i,root)}}}$

剩下的部分和幻想乡那道题就一样了。

代码：

 

1 #include
     
        2 #include
      
         3 #include
       
          4 typedef long long lnt;  5 const int N=200010;  6 struct pnt{  7     int hd;  8     int fa;  9     int dp; 10     int wgt; 11     lnt val; 12     lnt sum; 13     lnt Sum; 14     int eind; 15     lnt diss; 16     lnt disf; 17     bool vis; 18 }p[N]; 19 struct ent{ 20     int twd; 21     int lst; 22 }e[N<<1]; 23 int rt; 24 int n,m; 25 int cnt; 26 int dfn; 27 int tdn; 28 int root; 29 int size; 30 int maxsize; 31 int lg[N<<2]; 32 int eula[N<<2][21]; 33 lnt w; 34 lnt V; 35 lnt val[N]; 36 void ade(int f,int t) 37 { 38     cnt++; 39     e[cnt].twd=t; 40     e[cnt].lst=p[f].hd; 41     p[f].hd=cnt; 42     return ; 43 } 44 void E_dfs(int x,int f) 45 { 46     eula[++dfn][0]=x; 47     p[x].eind=dfn; 48     p[x].dp=p[f].dp+1; 49     for(int i=p[x].hd;i;i=e[i].lst) 50     { 51         int to=e[i].twd; 52         if(to==f) 53             continue; 54         E_dfs(to,x); 55         p[x].wgt+=p[to].wgt; 56         eula[++dfn][0]=x; 57     } 58     return ; 59 } 60 void Add_dfs(int x,int f) 61 { 62     p[x].Sum=p[x].val; 63     for(int i=p[x].hd;i;i=e[i].lst) 64     { 65         int to=e[i].twd; 66         if(to==f) 67             continue; 68         Add_dfs(to,x); 69         p[x].Sum+=p[to].Sum; 70     } 71     V+=p[x].Sum*(w-p[x].Sum); 72     return ; 73 } 74 int Emin(int x,int y) 75 { 76     return p[x].dp
        
         y) 83         std::swap(x,y); 84     int l=lg[y-x+1]; 85     return Emin(eula[x][l],eula[y-(1<
         
          >1]+1;171     for(int i=1;i<=20;i++)172         for(int j=1;j+(1<
          
           <=dfn;j++)173 eula[j][i]=Emin(eula[j][i-1],eula[j+(1<<(i-1))][i-1]);174 root=0;175 size=n;176 maxsize=0x3f3f3f3f;177 grc_dfs(1,1);178 rt=root;179 bin_dfs(root,0);180 for(int i=1;i<=n;i++)181 {182 scanf("%lld",&p[i].val);183 update(i,p[i].val);184 w+=p[i].val;185 }186 Add_dfs(1,1);187 while(m--)188 {189 int cmd;190 scanf("%d",&cmd);191 if(cmd==1)192 {193 int x,y;194 scanf("%d%d",&x,&y);195 lnt dv=y-p[x].val;196 update(x,dv);197 V+=dv*Query(x);198 w+=dv;199 p[x].val=y;200 }else{201 int x;202 scanf("%d",&x);203 lnt ans=-V+w*w;204 ans+=Query(x)*w;205 printf("%lld\n",ans);206 }207 }208 return 0;209 }