Description：

一棵 $n$ 个点有点权的树。 $q$ 次操作，每次修改一个点的点权或询问以某个点为根时每棵子树点权和的平方和。

$1\leqslant n\leqslant 200000$

Solution：

正解太难想到。

设 $s_i$ 表示子树的点权和， $sum$ 为总的点权和。

首先观察式子： $$ \sum_{i=1}^n\sum_{j=1}^nv_iv_jdis_{i,j} $$ 它的含义是对于每对点，把他们之间所有边（共 $dis_{i,j}$ 条）的边权都加上 $v_i\times v_j$ 然后求和。

然后发现上面那个式子等价于： $$ \sum_{i=1}^ns_i(sum-s_i) $$ 大概就是枚举所有点的父亲的边，然后统计这条边的贡献，根节点不会产生贡献所以不用计算。

化一下式子会发现： $$ W=\sum_{i=1}^nv_i(\sum_{j=1}^nv_jdis_{i,j})=sum\sum_{i=1}^ns_i-\sum_{i=1}^ns_i^2 $$ 设 $\begin{align}calc(k)=\sum_{i=1}^nv[i]\times dis_{i,k}\end{align}$ ，这个是可以用动态点分治 $O(\log n)$ 求的，那对某个点进行修改 $W$ 的变化量为： $$ \Delta W=2\Delta v\times calc(k) $$ 还有最后一个问题，就是 $\begin{align}\sum_{i=1}^ns_i\end{align}$ 怎么计算，发现这个其实就是 $calc(k)$ ，因为 $calc(k)$ 的定义可以看成是对从他到根的每个点都有 $v[i]$ 的贡献，把这个求和。

所以这个式子的所有部分都已知，反解出 $ans$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

#define MAXN 200010

int v[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int fa[MAXN],siz[MAXN],top[MAXN],dep[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int dis(int a,int b)

{

	return dep[a] + dep[b] - 2 * dep[LCA(a,b)];

}

int size[MAXN],d[MAXN],s,root;

#define INF 0x3f3f3f3f

bool vis[MAXN];

void getroot(int k,int fa)

{

	size[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		size[k] += size[e[i].to];

		d[k] = max(d[k],size[e[i].to]);

	}

	d[k] = max(d[k],s - size[k]);

	if(d[k] < d[root])root = k;

	return;

}

typedef long long ll;

int anc[MAXN],sum[MAXN],tofa[MAXN],tot[MAXN];

void divide(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		s = size[e[i].to];root = 0;

		getroot(e[i].to,0);

		anc[root] = k;

		divide(root);

	}

	return;

}

void modify(int k,int v)

{

	tot[k] += v;

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		int dist = dis(k,anc[i]);

		tofa[i] += dist * v;

		sum[anc[i]] += dist * v;

		tot[anc[i]] += v;

	}

	return;

}

int calc(int k)

{

	int res = sum[k];

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		int dist = dis(k,anc[i]);

		res += (tot[anc[i]] - tot[i]) * dist + sum[anc[i]] - tofa[i];

	}

	return res;

}

ll W = 0;

int main()

{

	scanf("%d%d",&n,&q);

	for(int i = 1;i < n;++i)add(rd(),rd());

	for(int i = 1;i <= n;++i)v[i] = rd();

	dfs1(1,1);dfs2(1,1);

	root = 0;d[0] = INF;s = n;

	getroot(1,0);

	int rt = root;

	divide(root);

	for(int i = 1;i <= n;++i)modify(i,v[i]);

	for(int i = 1;i <= n;++i)W += 1ll * v[i] * calc(i);

	W /= 2;

	int opt,x,y;

	for(int i = 1;i <= q;++i)

	{

		opt = rd();

		if(opt == 1)

		{

			x = rd();y = rd();

			W += 1ll * (y - v[x]) * calc(x);

			modify(x,y - v[x]);

			v[x] = y;

		}

		else

		{

			x = rd();

			printf("%lld\n",1ll * tot[rt] * (calc(x) + tot[rt]) - W);

		}

	}

	return 0;

}