Snacks
Time Limit: 10000/5000 MS(Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 705 Accepted Submission(s):151
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零食机的路线中，价值总和的最大值。
SampleInput
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
SampleOutput
Case #1:
102
27
2
20
Source
2016"百度之星" - 初赛（Astar Round2A）
【解题思路】
必须到经过这个点，意思就是说是从这个点的子树中找一个最大值，所以dfs序线段树维护最大值，修改即区间修改。
【代码】
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<ctime> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<set> #include<map> #include<vector> #include<queue> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif #define CLOCK CLOCKS_PER_SEC #define cle(x) memset(x,0,sizeof(x)) #define maxcle(x) memset(x,0x3f,sizeof(x)) #define mincle(x) memset(x,-1,sizeof(x)) #define maxx(x1,x2,x3) max(x1,max(x2,x3)) #define minn(x1,x2,x3) min(x1,min(x2,x3)) #define cop(a,x) memcpy(x,a,sizeof(a)) #define FROP "hdu" #define LL long long #define smin(x,tmp) x=min(x,tmp) #define smax(x,tmp) x=max(x,tmp) using namespace std; const LL INF = 1e18; const int N = 1e5+10000; struct ii { int to,ne; ii(int to=0,int ne=0):to(to),ne(ne){ } }ed[N*2]; int fa[N],tii[N],tio[N],Index=0,head[N],val[N],_tii[N]; LL dis[N]; struct Node { LL mx; LL lazy; }node[N*4]; #define mx(x) node[x].mx #define lazy(x) node[x].lazy #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r void dfs(int u,LL d) { tii[u]=++Index; _tii[Index]=u; dis[u]=d; for(int i = head[u]; i; i=ed[i].ne) { int v=ed[i].to; if(v==fa[u])continue; fa[v]=u; dfs(v,d+val[v]); } tio[u]=Index; } void build(int rt,int l,int r) { if(l==r) { mx(rt)=dis[_tii[l]]; return; } int mid=(l+r)>>1; build(lson); build(rson); mx(rt)=max(mx(rt<<1),mx(rt<<1|1)); } void pushdown(int rt) { if(lazy(rt)==0)return; lazy(rt<<1)+=lazy(rt); lazy(rt<<1|1)+=lazy(rt); mx(rt<<1)+=lazy(rt); mx(rt<<1|1)+=lazy(rt); lazy(rt)=0; } void modify(int rt,int l,int r,int L,int R,LL v) { if(l>=L&&r<=R) { mx(rt)+=v; lazy(rt)+=v; return; } pushdown(rt); int mid=(l+r)>>1; if(mid>=L)modify(lson,L,R,v); if(mid<R)modify(rson,L,R,v); mx(rt)=max(mx(rt<<1),mx(rt<<1|1)); } LL query(int rt,int l,int r,int L,int R) { if(l>=L&&r<=R)return mx(rt); pushdown(rt); int mid=(l+r)>>1; LL res=-INF; if(mid>=L)smax(res,query(lson,L,R)); if(mid<R)smax(res,query(rson,L,R)); return res; } int n,m,T; void init() { cle(ed),cle(head); cle(fa),Index=0,cle(node); cle(dis),cle(tii),cle(tio),cle(val); scanf("%d%d",&n,&m); for(int i = 1; i <= n-1; i++) { int x,y; scanf("%d%d",&x,&y); ed[i*2-1]=ii(y+1,head[x+1]); head[x+1]=i*2-1; ed[i*2]=ii(x+1,head[y+1]); head[y+1]=i*2; } for(int i = 1; i <= n; i++) scanf(AUTO,&val[i]); } int kase; int main() { freopen(FROP".in","r",stdin); freopen(FROP".out","w",stdout); scanf("%d",&T); for(int i = 1;i <= T; i++) { printf("Case #%d:\n",++kase); init(); dfs(1,val[1]); build(1,1,n); for(int i = 1; i <= m;i++) { int x; scanf("%d",&x); if(x) { int c; scanf("%d",&c); printf(AUTO"\n",query(1,1,n,tii[c+1],tio[c+1])); } else { int a,b; scanf("%d%d",&a,&b); if(b^val[a+1])modify(1,1,n,tii[a+1],tio[a+1],(LL)b-val[a+1]);//a+1! val[a+1]=b;//修改了记住更新！ } } } return 0; }
，，，记住更新后要重新赋值，，不然！
