难度：NOI/NOI+/CTSC

题目描述

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

输入格式

        第一行两个整数n、q。
        接下来n-1行每行两个整数a和b，表示树中a与b之间有一条边，保证给出的边不会重复。
        接下来一行n个整数，第i个整数表示第i个点的点权。
        接下来q行每行两或三个数，如果第一个数为1，那么接下来有两个数x和y，表示将第x个点的点权修改为y，如果第一个数为2，那么接下来有一个数x，表示询问以x为根时每棵子树点权和的平方和。

输出格式

        对于每个询问输出答案。

输入输出样例

Sample input

4 5
1 2
2 3
2 4
4 3 2 1
2 2
1 1 3
2 3
1 2 4
2 4

Sample output

121
140
194

说明

        对于100%的数据，$1 \leq n,q \leq 200000$, $−10≤$输入的每个点权$\leq 10$。

题解

        直接求不好求，考虑以1为根时，给某个结点点权加上$a$对答案的贡献。假设一开始子树$i$的点权和为$s_i$。
        显然给修改一个结点的点权，只会影响其到根这一段路径$P$上的子树点权和，其贡献为：

        化简这个式子，得到：

        维护一下每一个点对应的子树点权和，求这条路径上的子树点权和之和以及结点数量就可以求出贡献。
        下面考虑换根。
        当换$x$为根时，容易发现只有从1号结点到$x$这一段路径上的结点的子树点权和发生了变化，设这一段路径为$P$，结点$i$在以1为根时的子树点权和为$a_i$，以$x$为根时的点权和为$b_i$。设路径$P$上从1开始到$x$这一段连续的路径结点为$k_1,k_2,\cdots,k_p$那么有：

        那么答案设为$Ans_x$，原有（以1为根）答案为$Ans_1$，则：

        然后拿数据结构维护上面的信息，这里用的LCT。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>

#define N 200005
using namespace std;
struct Node {
    int ch[2], fa, num, la1;
    long long sum, v, la2;
} nd[N];
int sta[N];

inline void update(int x) {
    nd[x].num = nd[nd[x].ch[0]].num + nd[nd[x].ch[1]].num + 1;
    nd[x].sum = nd[nd[x].ch[0]].sum + nd[nd[x].ch[1]].sum + nd[x].v;
}

inline void change(int f, int s, int w) {
    nd[f].ch[w] = s, nd[s].fa = f;
}

inline bool isNotRoot(int x) {
    return nd[nd[x].fa].ch[0] == x || nd[nd[x].fa].ch[1] == x;
}

inline int identify(int x) {
    return nd[nd[x].fa].ch[1] == x;
}

inline void pushr(int x) {
    swap(nd[x].ch[0], nd[x].ch[1]), nd[x].la1 ^= 1;
}

inline void pushd(int x) {
    if (nd[x].la1)pushr(nd[x].ch[0]), pushr(nd[x].ch[1]), nd[x].la1 = 0;
    if (nd[x].la2) {
        if (nd[x].ch[0]) {
            nd[nd[x].ch[0]].v += nd[x].la2, nd[nd[x].ch[0]].sum += nd[nd[x].ch[0]].num * nd[x].la2;
            nd[nd[x].ch[0]].la2 += nd[x].la2;
        }
        if (nd[x].ch[1]) {
            nd[nd[x].ch[1]].v += nd[x].la2, nd[nd[x].ch[1]].sum += nd[nd[x].ch[1]].num * nd[x].la2;
            nd[nd[x].ch[1]].la2 += nd[x].la2;
        }
        nd[x].la2 = 0;
    }
}

inline void rotate(int x) {
    int f = nd[x].fa, g = nd[f].fa, i = identify(x), j = identify(f);
    if (isNotRoot(f))change(g, x, j);
    else nd[x].fa = g;
    change(f, nd[x].ch[i ^ 1], i), change(x, f, i ^ 1), update(f), update(x);
}

inline void splay(int x) {
    int i = 0, y = x;
    sta[++i] = y;
    while (isNotRoot(y))sta[++i] = y = nd[y].fa;
    while (i)pushd(sta[i--]);
    while (isNotRoot(x)) {
        int f = nd[x].fa;
        if (isNotRoot(f)) {
            if (identify(x) == identify(f))rotate(f);
            else rotate(x);
        }
        rotate(x);
    }
}

inline void access(int x) {
    for (int i = 0; x; x = nd[i = x].fa)splay(x), nd[x].ch[1] = i, update(x);
}

inline void makeRoot(int x) {
    access(x), splay(x), pushr(x);
}

inline void link(int x, int y) {
    makeRoot(x), nd[x].fa = y;
}

int n, q;
long long v[N], ans;

inline void split(int x) {//切出1~x树链
    makeRoot(1), access(x), splay(x);
}

inline void add(int x, long long k) {//结点x点权加k
    split(x), ans += k * k * nd[x].num + 2 * k * nd[x].sum;
    nd[x].v += k, nd[x].sum += nd[x].num * k, nd[x].la2 += k;
}


inline int read() {
    char e = getchar();
    int s = 0, g = 0;
    while (e < '-')e = getchar();
    if (e == '-')g = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return g ? -s : s;
}

int main() {
    n = read(), q = read();
    for (int i = 1; i < n; i++)link(read(), read());
    for (int i = 1; i <= n; i++)add(i, v[i] = read());
    while (q--) {
        int opt = read(), x;
        long long y;
        if (opt == 1) x = read(), y = read(), add(x, y - v[x]), v[x] = y;
        else {
            split(x = read()), splay(1), y = nd[1].v, splay(x);
            printf("%lld\n", ans + y * ((nd[x].num + 1) * y - 2 * nd[x].sum));
        }
    }
    return 0;
}