百度科技园内有nn个零食机,零食机之间通过n−1n−1条路相互连通。每个零食机都有一个值vv,表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充,零食机的价值vv会时常发生变化。小度熊只能从编号为0的零食机出发,并且每个零食机至多经过一次。另外,小度熊会对某个零食机的零食有所偏爱,要求路线上必须有那个零食机。
为小度熊规划一个路线,使得路线上的价值总和最大。
Input输入数据第一行是一个整数T(T≤10)T(T≤10),表示有TT组测试数据。
对于每组数据,包含两个整数n,m(1≤n,m≤100000)n,m(1≤n,m≤100000),表示有nn个零食机,mm次操作。
接下来n−1n−1行,每行两个整数xx和y(0≤x,y<n)y(0≤x,y<n),表示编号为xx的零食机与编号为yy的零食机相连。
接下来一行由nn个数组成,表示从编号为0到编号为n−1n−1的零食机的初始价值v(|v|<100000)v(|v|<100000)。
接下来mm行,有两种操作:0 x y0 x y,表示编号为xx的零食机的价值变为yy;1 x1 x,表示询问从编号为0的零食机出发,必须经过编号为xx零食机的路线中,价值总和的最大值。
本题可能栈溢出,辛苦同学们提交语言选择c++,并在代码的第一行加上:
`#pragma comment(linker, “/STACK:1024000000,1024000000”) `Output对于每组数据,首先输出一行”Case #?:”,在问号处应填入当前数据的组数,组数从1开始计算。
对于每次询问,输出从编号为0的零食机出发,必须经过编号为xx零食机的路线中,价值总和的最大值。
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序可以将对子树的操作转化为对区间的操作,线段树
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<string> #include<cstring> using namespace std; typedef long long LL; const int MAXN = 100002; //一开始全部Insert一遍然后再操作 struct node { LL l,r; LL max;//子树中最大的节点 LL laz; }T[MAXN*4+9]; struct edge { LL v,next; }E[MAXN]; LL head[MAXN], cnt, index; LL b[MAXN],e[MAXN], val[MAXN]; LL range[MAXN]; LL n, m; void init() { index = cnt = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v) { E[cnt].v = v; E[cnt].next = head[u]; head[u] = cnt++; } void dfs(int u,int pre) { b[u] = index++; range[u] = index - 1; for(int i = head[u];i!=-1;i = E[i].next) { if(E[i].v==pre) continue; dfs(E[i].v,u); } e[u] = index; } void pushdown(LL x) { if(T[x].laz) { T[x*2].laz += T[x].laz; T[x*2+1].laz += T[x].laz; T[x*2].max += T[x].laz; T[x*2+1].max += T[x].laz; T[x].laz = 0; } } void pushup(LL x) { T[x].max = max(T[x*2].max,T[x*2+1].max); } void build(LL x,LL l,LL r) { T[x].l = l ,T[x].r = r,T[x].laz = 0, T[x].max = 0; if(l==r) return; LL mid = (l + r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); pushup(x); } void update(LL x,LL l,LL r,LL val) { if(T[x].l == l && T[x].r == r) { T[x].max += val; T[x].laz += val; return ; } pushdown(x); LL mid = (T[x].l + T[x].r)/2; if(r<=mid) update(x*2,l,r,val); else if(l>mid) update(x*2+1,l,r,val); else { update(x*2,l,mid,val); update(x*2+1,mid+1,r,val); } pushup(x); } LL query(LL x, LL l, LL r) { if(T[x].l == l && T[x].r == r) { return T[x].max; } pushdown(x); LL mid = ( T[x].l + T[x].r)/2; if(r<=mid) return query(x*2,l,r); else if(l>mid) return query(x*2+1,l,r); else return max(query(x*2,l,mid),query(x*2+1,mid+1,r)); } int main() { int cas = 1; LL tt; scanf("%lld",&tt); while(tt--) { init(); LL op,f,t; scanf("%lld%lld",&n,&m); for(LL i= 0;i<n - 1;i++) { scanf("%lld%lld",&f,&t); addedge(f,t); addedge(t,f); } dfs(0,-1); for(int i = 0;i<n;i++) scanf("%lld",&val[i]); build(1,0,n-1); for(int i= 0;i<n;i++) update(1,b[i],e[i]-1,val[i]); printf("Case #%d: ",cas++); while(m--) { scanf("%lld",&op); if(op==0) { scanf("%lld%lld",&f,&t);//把f点的价值修改为t update(1,b[f],e[f]-1,t-val[f]); val[f] = t; } else if(op==1) { scanf("%lld",&f);//查询x点子树最大值 printf("%lld ",query(1,b[f],e[f]-1)); } } } }
最新评论