image.png
    image.png

    1. #include <bits/stdc++.h>
    3. using namespace std;
    5. typedef long long LL;
    6. const int N = 100010, M = N*2;
    8. int n, m, idx;
    9. vector<int> T[N];
    10. //id[i]: 原数组每个点的编号 
    11. //nw[i]: dfs序列中第i个点的编号 
    12. int id[N], nw[N], w[N];
    13. //top[i]: i点所在重链的顶点编号
    14. //son[i]: i点的重儿子 
    15. int dep[N], sz[N], top[N], fa[N], son[N];
    17. struct node {
    18.     int l, r;
    19.     LL add, sum;
    20. };
    21. struct SegTree {
    22.     node tr[N*4];
    24.     void inline pushup(int u) {
    25.         tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
    26.     }
    28.     void inline eval(node& t, int add) {
    29.         t.sum += add*(t.r-t.l+1);
    30.           t.add += add; 
    31.     }
    33.     void inline pushdown(int u) {
    34.         if (tr[u].add) {
    35.             eval(tr[u<<1], tr[u].add);
    36.             eval(tr[u<<1|1], tr[u].add);
    37.             tr[u].add = 0;
    38.         }
    39.     }
    41.     void build(int u, int l, int r) {
    42.         tr[u] = {l, r, 0, nw[r]};
    43.         if (l == r) return;
    44.         int mid = l+r>>1;
    45.         build(u<<1, l, mid);
    46.         build(u<<1|1, mid+1, r);
    47.         pushup(u);
    48.     }
    50.     void update(int u, int l, int r, int k) {
    51.         if (l<=tr[u].l && r>=tr[u].r) {
    52.             eval(tr[u], k);
    53.             return;
    54.         }
    55.         pushdown(u);
    56.         int mid = tr[u].l+tr[u].r>>1;
    57.         if (l <= mid) 
    58.             update(u<<1, l, r, k);
    59.         if (r > mid) 
    60.             update(u<<1|1, l, r, k);
    61.         pushup(u);
    62.     }
    64.     LL query(int u, int l, int r) {
    65.         if (l <= tr[u].l && r >= tr[u].r) 
    66.             return tr[u].sum;
    67.         pushdown(u);
    68.         int mid = tr[u].l+tr[u].r>>1;
    69.         LL res = 0;
    70.         if (l <= mid) 
    71.             res += query(u<<1, l, r);
    72.         if (r > mid) 
    73.             res += query(u<<1|1, l, r);
    74.         return res;
    75.     }
    76. }ST;
    78. void dfs1(int u, int father, int depth) {
    79.     dep[u] = depth, fa[u] = father, sz[u] = 1;
    80.     for (int i = 0; i < T[u].size(); i++) {
    81.         int j = T[u][i];
    82.         if (j == father)
    83.             continue;
    84.         dfs1(j, u, depth + 1);
    85.         sz[u] += sz[j];
    86.         if (sz[son[u]] < sz[j]) 
    87.             son[u] = j;
    88.     }
    89. }
    91. void dfs2(int u, int t) {
    92.     //t: 当前点所在重链的顶点 
    93.     id[u] = ++idx, nw[idx] = w[u], top[u] = t;
    94.     if (!son[u]) 
    95.         return;
    96.     //优先搜索重儿子 
    97.     dfs2(son[u], t);
    98.     for (int i = 0; i < T[u].size(); i++) {
    99.         int j = T[u][i];
    100.         if (j==fa[u] || j==son[u]) 
    101.             continue;
    102.         //搜轻儿子，轻儿子重链顶点就是本身 
    103.         dfs2(j, j);
    104.     }
    105. }
    107. void update_path(int u, int v, int k) {
    108.     //若两个点不在同一重链中 
    109.     while (top[u] != top[v]) {
    110.         if (dep[top[u]] < dep[top[v]]) 
    111.             swap(u, v);
    112.         ST.update(1, id[top[u]], id[u], k);
    113.         u = fa[top[u]];
    114.     } 
    115.     if (dep[u] < dep[v])
    116.         swap(u, v);
    117.     ST.update(1, id[v], id[u], k);
    118. }
    120. LL query_path(int u, int v) {
    121.     LL res = 0;
    122.     while (top[u] != top[v]) {
    123.         if (dep[top[u]] < dep[top[v]]) swap(u, v);
    124.         res += ST.query(1, id[top[u]], id[u]);
    125.         u = fa[top[u]];
    126.     }
    127.     if (dep[u] < dep[v]) swap(u, v);
    128.     res += ST.query(1, id[v], id[u]);
    129.     return res;
    130. }
    132. void update_tree(int u, int k) {
    133.     ST.update(1, id[u], id[u]+sz[u]-1, k);
    134. }
    136. LL query_tree(int u) {
    137.     return ST.query(1, id[u], id[u]+sz[u]-1);
    138. }
    140. int main() {
    141.     scanf("%d", &n);
    142.     for (int i = 1; i <= n; i++) 
    143.         scanf("%d", &w[i]);
    144.     for (int i = 0; i < n-1; i++) {
    145.         int u, v;
    146.         scanf("%d%d", &u, &v);
    147.         T[u].push_back(v);
    148.         T[v].push_back(u);
    149.     }
    150.     //第一遍dfs找出每个点的重儿子 
    151.     dfs1(1, -1, 1);
    152.     //第二遍dfs求dfs序 
    153.     dfs2(1, 1);
    154.     ST.build(1, 1, n);
    155.     scanf("%d", &m);
    156.     while (m--) {
    157.         int t, u, v, k;
    158.         scanf("%d%d", &t, &u);
    159.         if (t == 1) {
    160.             scanf("%d%d", &v, &k);
    161.             update_path(u, v, k);
    162.         } else if (t == 2) {
    163.             scanf("%d", &k);
    164.             update_tree(u, k);
    165.         } else if (t == 3) {
    166.             scanf("%d", &v);
    167.             printf("%lld\n", query_path(u, v));
    168.         } else {
    169.             printf("%lld\n", query_tree(u));    
    170.         }
    171.     }
    172.     return 0;
    173. }