HDU5692 Snacks
Problem Description
百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。每个零食机都有一个值v，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
Input
输入数据第一行是一个整数T(T≤10)，表示有T组测试数据。
对于每组数据，包含两个整数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序+线段树
题目要求修改点值和从0出发经过s点的最大权值和。
实质是求s点的子树中dis最大的，因为某一子树dfs序是连续的，所以该问题成了区间求最大值和区间修改。
修改某个点等价于将以这个点为根的最大值加上一个数。
代码：WA的..没调完...
WA的原因
1、修改错点了，应该是价值改，我改的价值的累加和....
2、修改完区间后...点没修改...
3、没用long long
4、md目前还是WA的。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #define maxn 200002 using namespace std; int t,n,m,od,sumedge,tim_node,kis,cnt; int head[maxn],bf[maxn],l[maxn],r[maxn]; long long dis[maxn],ans[maxn],sum[maxn]; struct TREE{ int l,r; long long maxx,s; }tr[maxn<<2]; struct Edge{ int x,y,nxt; Edge(int x=0,int y=0,int nxt=0): x(x),y(y),nxt(nxt){} }edge[maxn<<1]; inline void add(int x,int y){ edge[++sumedge]=Edge(x,y,head[x]); head[x]=sumedge; } void dfs(int x,int fa){ bf[tim_node]=x;l[x]=tim_node++; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; if(v==fa)continue; dis[v]+=dis[x]; dfs(v,x); } r[x]=tim_node-1; } inline void pushup(int p){ tr[p].maxx=max(tr[p<<1].maxx,tr[p<<1|1].maxx); } inline void pushdown(int rt){ if(tr[rt].s==0)return; tr[rt<<1].s+=tr[rt].s;tr[rt<<1|1].s+=tr[rt].s; tr[rt<<1].maxx+=tr[rt].s;tr[rt<<1|1].maxx+=tr[rt].s; tr[rt].s=0; } void build(int rt,int l,int r){ tr[rt].l=l;tr[rt].r=r; if(l==r){ tr[rt].maxx=dis[bf[l]]; return; } int mid=(l+r)>>1; build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); pushup(rt); } void change(int rt,int l,int r,int qx,int qy,int z){ if(qx<=l&&qy>=r){ tr[rt].maxx+=z; tr[rt].s+=z; return; } int mid=(l+r)>>1; if(qy<=mid)change(rt<<1,l,mid,qx,qy,z); else if(qx>mid)change(rt<<1|1,mid+1,r,qx,qy,z); else { change(rt<<1,l,mid,qx,mid,z); change(rt<<1|1,mid+1,r,mid+1,qy,z); } } long long query(int rt,int l,int r,int qx,int qy){ pushdown(rt); if(qx<=l&&qy>=r)return tr[rt].maxx; int mid=(l+r)>>1; if(qy<=mid)return query(rt<<1,l,mid,qx,qy); else if(qx>mid)return query(rt<<1|1,mid+1,r,qx,qy); else return max(query(rt<<1,l,mid,qx,mid),query(rt<<1|1,mid+1,r,mid+1,qy)); } int main(){ scanf("%d",&t); while(t--){ memset(head,0,sizeof(head)); sumedge=0;tim_node=0;cnt=0; scanf("%d%d",&n,&m); int x;long long y; for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); add(x,y);add(y,x); } for(int i=0;i<n;i++){ cin>>dis[i];sum[i]=dis[i]; } dfs(0,-1); build(1,0,n-1); for(int i=1;i<=m;i++){ scanf("%d",&od); if(od==0){ scanf("%d%lld",&x,&y); change(1,0,n-1,l[x],r[x],y-sum[x]); sum[x]=y; }else { scanf("%d",&x); ans[++cnt]=query(1,0,n-1,l[x],r[x]); } } if(cnt){ printf("Case #%d: ",++kis); for(int i=1;i<=cnt;i++)printf("%lld ",ans[i]); } } return 0; }