题目链接：
Problem Description
百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。每个零食机都有一个值v，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
Input
输入数据第一行是一个整数T(T≤10)，表示有TT组测试数据。
对于每组数据，包含两个整数n,m(1≤n,m≤100000)，表示有n个零食机，m次操作。
接下来n−1行，每行两个整数x和y(0≤x,y<n)，表示编号为x的零食机与编号为y的零食机相连。
接下来一行由n个数组成，表示从编号为0到编号为n-1的零食机的初始价值v(∣v∣<100000)。
接下来m行，有两种操作：0 x y，表示编号为x的零食机的价值变为y；1 x，表示询问从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：
#pragma comment(linker, "/STACK:1024000000,1024000000")
Output
对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。
对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
Sample Input
1
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5
Sample Output
Case #1:
102
27
2
20 题意： 思路： 先把这棵树dfs求出距离并弄成线段树,l[x],r[x]分别表示x的子树节点的左右区间,每次修改[l[x],r[x]]这个区间,用线段树的区间修改,然后就好啦; AC代码：
#include <bits/stdc++.h>
/*
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
*/
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=1e5+;
int n,m,head[N],l[*N],r[*N],cnt,num;
LL dis[N],b[N],va[N];
struct Edge
{
int to,next;
}edge[*N];
void add_edge(int s,int e)
{
edge[cnt].next=head[s];
edge[cnt].to=e;
head[s]=cnt++;
}
void dfs(int x,int fa)
{
num++;
b[num]=dis[x];
l[x]=num;
for(int i=head[x];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(y!=fa)
{
dis[y]=dis[x]+va[y];
dfs(y,x);
}
}
r[x]=num;
}
struct Tree
{
int l,r;
LL ans,lazy;
}tr[*N];
void pushup(int o)
{
tr[o].ans=max(tr[*o].ans,tr[*o+].ans);
}
void pushdown(int o)
{
if(tr[o].lazy)
{
tr[*o].ans+=tr[o].lazy;
tr[*o+].ans+=tr[o].lazy;
tr[*o].lazy+=tr[o].lazy;
tr[*o+].lazy+=tr[o].lazy;
tr[o].lazy=;
}
}
void build(int o,int L,int R)
{
tr[o].l=L;
tr[o].r=R;
tr[o].lazy=;
if(L>=R)
{
tr[o].ans=b[L];
return ;
}
int mid=(L+R)>>;
build(*o,L,mid);
build(*o+,mid+,R);
pushup(o);
}
void update(int o,int L,int R,LL val)
{
if(L<=tr[o].l&&R>=tr[o].r)
{
tr[o].ans=tr[o].ans+val;
tr[o].lazy=tr[o].lazy+val;
return ;
}
int mid=(tr[o].l+tr[o].r)>>;
pushdown(o);
if(R<=mid)update(*o,L,R,val);
else if(L>mid)update(*o+,L,R,val);
else
{
update(*o,L,mid,val);
update(*o+,mid+,R,val);
}
pushup(o);
}
LL query(int o,int L,int R)
{
if(L<=tr[o].l&&tr[o].r<=R)return tr[o].ans;
int mid=(tr[o].l+tr[o].r)>>;
pushdown(o);
if(R<=mid)return query(o*,L,R);
else if(L>mid)return query(o*+,L,R);
else return max(query(*o,L,mid),query(*o+,mid+,R));
}
int main()
{
int t;
scanf("%d",&t);
int Case=;
while(t--)
{
printf("Case #%d:\n",Case++);
cnt=;
num=;
mst(head,-);
scanf("%d%d",&n,&m);
int u,v;
Riep(n-)
{
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
Riop(n)scanf("%I64d",&va[i]);
dis[]=va[];
dfs(,-);
build(,,num);
int flag,x,y;
Riep(m)
{
scanf("%d",&flag);
if(flag)
{
scanf("%d",&x);
printf("%I64d\n",query(,l[x],r[x]));
}
else
{
scanf("%d%d",&x,&y);
update(,l[x],r[x],(LL)y-va[x]);
va[x]=(LL)y;
}
}
}
return ;
}