解题思路

这个题还是挺巧妙的。首先我们要明确一下题目中的操作。

第一种操作是单点更新。第二种操作是查询从 0 号结点（树根）开始且必需经过 x 号结点的路径上，数值和最大是多少。

接下来我们先根据第二种操作来把题目要求进行一些转化。既然是要求路径上数值和最大，那么可以先找到可能的路径有哪些.很容易看出可能的路径肯定是 0 到 x 或 0 到 x 的子结点。我们可以在输入完成后将 0 到任意结点的路径数值和都预处理出来，并用 DFS 序处理结点在数组中的分布以使子树结点连续。这样第二种操作就转化成了一个区间查询最大值的操作，我们可以用线段树来实现。

第二种操作分析完后，我们再回头来看第一种操作，它要求实现单点更新。在上一段我们已经通过建模得到了一个保存路径数值和的数组，一旦树上某个结点的数值更新，就意味着它和它的所有子结点到 0 的路径数值和都要更新，而他们的改变量都是一样的，因此我们计算出这个结点的改变量，就可以应用线段树区间更新来对所有受影响的点都进行同步更新。这样就实现了第一种操作的需求。

参考代码

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const long long INF = 1e18;
const int MAXN = 100001;

struct edge {
    int to;
    int next;
} e[MAXN<<1];

int t, n, m, op, x, y;
long long a[MAXN], sum[MAXN], val;
int head[MAXN], cnt;
int in[MAXN], out[MAXN], idx, mp[MAXN];
long long st[MAXN<<2], lazy[MAXN<<2];

void Add(int u, int v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void DFS(int u, int pre) {
    in[u] = ++idx;
    mp[idx] = u;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(v != pre) {
            sum[v] = sum[u]+a[v];
            DFS(v, u);
        }
    }
    out[u] = idx;
}

void PushUp(int rt) {
    st[rt] = max(st[rt<<1], st[rt<<1|1]);
}

void PushDown(int rt, int m) {
    if(lazy[rt]) {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        st[rt<<1] += lazy[rt];
        st[rt<<1|1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void Build(int l, int r, int rt) {
    lazy[rt] = 0;
    if(l== r) {
        st[rt] = sum[mp[l]];
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

void Update(int L, int R, long long v, int l, int r, int rt) {
    if(L<=l && r<=R) {
        lazy[rt] += v;
        st[rt] += v;
        return;
    }
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    if(L <= m) Update(L, R, v, lson);
    if(R > m) Update(L, R, v, rson);
    PushUp(rt);
}

long long Query(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return st[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    long long ret = -INF;
    if(L <= m) ret = max(ret, Query(L, R, lson));
    if(R > m) ret = max(ret, Query(L, R, rson));

    return ret;
}

int main(int argc, char const *argv[]) {
    scanf("%d", &t);
    for(int cs=1; cs<=t; ++cs) {
        idx = cnt = 0;
        memset(head, -1, sizeof head);
        scanf("%d %d", &n, &m);
        for(int i=0; i<n-1; ++i) {
            scanf("%d %d", &x, &y);
            x++;
            y++;
            Add(x, y);
            Add(y, x);
        }
        for(int i=1; i<=n; ++i) {
            scanf("%lld", &a[i]);
        }
        sum[1] = a[1];
        DFS(1, -1);
        Build(1, n, 1);
        printf("Case #%d:\n", cs);
        while(m--) {
            scanf("%d", &op);
            if(op == 0) {
                scanf("%d %lld", &x, &val);
                x++;
                Update(in[x], out[x], val-a[x], 1, n, 1);
                a[x] = val;
            }
            else {
                scanf("%d", &x);
                x++;
                printf("%lld\n", Query(in[x], out[x], 1, n, 1));
            }
        }
    }
    
    return 0;
}