hdu 5692(dfs序+线段树,好题)
Snacks
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1660 Accepted Submission(s): 403
Problem Description
百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。每个零食机都有一个值v，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
Input
输入数据第一行是一个整数T，表示有T组测试数据。
对于每组数据，包含两个整数n,m(1≤n,m≤100000)，表示有n个零食机，m次操作。
接下来n−1行，每行两个整数x和y，表示编号为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
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
102
27
2
20
Source
百度之星初赛的时候当时没做出来,现在练习DFS序,知道是线段树+dfs序感觉就容易了,都是套路,感觉非常厉害的题目.
利用dfs序将树转换成了线段树.我们保存一个从根节点到每个子节点的前缀和,所以将其转换成线段树之后就对于原来的某个结点,其最大值就是从0到它+它到它的所有子结点中最大的那一个。转换成线段树之后直接进行区间查找,然后每次改变其值也只需要成段更新即可..但是成段更新不能够更新到叶子结点,那样会超时,所以只能更新到段为止,所以要加Pushdown操作.
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N =100005; const LL INF = 1e18; struct Edge{ int v,next; }edge[N<<2]; int head[N],tot,cnt; int in[N],out[N]; LL lazy[N<<2]; LL sum[N<<2],cost[N]; ///sum 存前缀和 LL dis[N],b[N]; int n,q; void init(){ memset(head,-1,sizeof(head)); tot = cnt = 0; } void addEdge(int u,int v,int &k){ edge[k].v = v,edge[k].next = head[u],head[u] = k++; } void dfs(int u,int pre){ in[u] = ++cnt; b[cnt] = dis[u]; ///原来的树的下标对应线段树的下标 for(int k=head[u];k!=-1;k=edge[k].next){ int v = edge[k].v; if(v==pre) continue; dis[v] = dis[u] + cost[v]; dfs(v,u); } out[u] = cnt; } void pushup(int idx){ sum[idx] = max(sum[idx<<1],sum[idx<<1|1]); } void pushdown(int idx) { if(lazy[idx]) { sum[idx << 1] += lazy[idx]; sum[idx << 1 | 1] += lazy[idx]; lazy[idx << 1] += lazy[idx]; lazy[idx << 1 | 1] += lazy[idx]; lazy[idx] = 0; } return; } void build(int l,int r,int idx){ lazy[idx] = 0; if(l==r){ sum[idx] = b[l]; return ; } int mid = (l+r)>>1; build(l,mid,idx<<1); build(mid+1,r,idx<<1|1); pushup(idx); } void update(int l,int r,int L,int R,int idx,int val){ if(l>=L&&r<=R){ sum[idx] =sum[idx] + val; lazy[idx] =lazy[idx] + val; return; } int mid = (l+r)>>1; pushdown(idx); if(mid>=L) update(l,mid,L,R,idx<<1,val); if(mid<R) update(mid+1,r,L,R,idx<<1|1,val); pushup(idx); } LL MAX = -1; void query(int l,int r,int L,int R,int idx){ if(l >= L&& r <= R){ MAX = max(MAX,sum[idx]); return ; } int mid = (l+r)>>1; pushdown(idx); if(mid>=L) query(l,mid,L,R,idx<<1); if(mid<R) query(mid+1,r,L,R,idx<<1|1); } int main() { int tcase,t=1; scanf("%d",&tcase); while(tcase--){ init(); scanf("%d%d",&n,&q); for(int i=0;i<n-1;i++){ int u,v; scanf("%d%d",&u,&v); addEdge(u,v,tot); addEdge(v,u,tot); } for(int i=0;i<n;i++){ scanf("%lld",&cost[i]); } dis[0] = cost[0]; dfs(0,-1); build(1,n,1); printf("Case #%d:\n",t++); while(q--){ int opr ,x, y; scanf("%d",&opr); if(opr==1){ scanf("%d",&x); MAX = -INF; query(1,n,in[x],out[x],1); printf("%lld\n",MAX); } else{ scanf("%d%d",&x,&y); LL change = (LL)y-cost[x]; ///这里累加变化量 update(1,n,in[x],out[x],1,change); cost[x] = y; } } } return 0; }
版权声明：本文为liyinggang原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。