【链接】
http://acm.hdu.edu.cn/showproblem.php?pid=5692
【题意】
树上两种操作：
0 x y 将x的权重变为y
1 x 求出从0出发，经过x的路径的最距离和
【分析】
其实就是求一棵子树x里到0点路径权值和最大的点的那个权值和，因为是对一棵子树的所有值，所以容易想到用DFS序来处理。
dfs序处理出2*n的数组，每个节点出现两次，以x为根的子树被包含在x出现的两次的区间中，第二次出现表示不选当前这个点。
每个节点第一次出现的位置记录一个它的价值v[i]，在第二次出现的位置记录一个-v[i]。那么子树中到根距离最多的点就是x那个区
间中前缀和最大的点。用线段树维护sum，mx(左前缀)
【代码】
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 6;
vector<int>v[maxn];
int in[maxn<<1], out[maxn<<1];
ll a[maxn<<1];
int cnt = 0;void dfs(int x,int f) {in[x] = ++cnt;for (int y : v[x])if(f!=y) {dfs(y, x);}out[x] = ++cnt;
}struct node {int l, r;ll sum, mx;
}t[maxn << 2];void build(int p, int l, int r) {t[p].l = l; t[p].r=r;if (l == r) { t[p].sum = t[p].mx = a[l]; return; }int mid = l + r >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;t[p].mx = max(t[p << 1].mx, t[p << 1].sum + t[p << 1 | 1].mx);
}void change(int p, int x, ll val) {if (t[p].l == t[p].r) {t[p].mx=t[p].sum = val;return;}int mid = t[p].l + t[p].r >> 1;if (x <= mid)change(p << 1, x, val);else change(p << 1 | 1, x, val);t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;t[p].mx = max(t[p << 1].mx, t[p << 1].sum + t[p << 1 | 1].mx);
}ll query(int p, int x, int y) {if (t[p].l==x&&t[p].r==y) return t[p].mx;int mid = t[p].l + t[p].r >> 1;if (y <= mid)return query(p << 1, x, y);else if (x > mid)return t[p<<1].sum+query(p << 1 | 1, x, y);else return max(query(p << 1, x, mid), t[p << 1].sum + query(p << 1 | 1, mid + 1, y));
}int main() {int t;scanf("%d", &t);int ca = 0;while (t--) {printf("Case #%d:\n", ++ca);int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)v[i].clear();for (int i = 1; i < n; i++) {int x, y;scanf("%d%d", &x, &y); x++; y++;v[x].push_back(y);v[y].push_back(x);}cnt = 0;dfs(1,1);for (int i = 1; i <= n; i++) {ll y;scanf("%lld", &y);a[in[i]] = y; a[out[i]] = -y;}build(1, 1, 2 * n);while (m--) {int op, x;ll y;scanf("%d%d", &op, &x);x++;if (op == 0) {scanf("%lld", &y);change(1, in[x], y);change(1, out[x], -y);}else {printf("%lld\n", query(1,in[x],out[x]-1));//注意out[x]表示已经走出x以及x的子树了}}}
}