Snacks
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1295 Accepted Submission(s): 302
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
对于每组数据，包含两个整数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") `
对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
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
#include<iostream>
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const int maxx = ;
int n,m;
int inf =0x7fffffff;
vector<int>edg[maxx];
long long val[maxx];
int l[maxx];
int r[maxx];
int index=;
int w[maxx];
long long tree[maxx<<];
long long add[maxx<<];
void build(int root,int l,int r)
{
add[root]=;
if(l==r)
{
tree[root]=val[l];
}
else
{
int mid=(l+r)>>;
build(root<<,l,mid);
build((root<<)+,mid+,r);
tree[root]=max(tree[root<<],tree[(root<<)+]);
} }
void push_down(int root,int nl,int nr)
{
if(add[root]!=)
{
add[root<<]+=add[root];
add[(root<<)+]+=add[root];
tree[root<<]+=add[root];
tree[(root<<)+]+=add[root];
add[root]=;
}
}
void update_interval(int root,int nl,int nr,int ul,int ur,int val)
{
if(add[root]!=) push_down(root,nl,nr);
//cout<<root<<endl;
if(nl==ul&&nr==ur)
{
tree[root]+=val;
add[root]+=val;
return;
}
int mid=(nl+nr)>>;
if(ur<=mid)
{
update_interval(root<<,nl,mid,ul,ur,val);
}
else if(ul>mid)
{
update_interval((root<<)+,mid+,nr,ul,ur,val);
}
else if(ul<=mid&&mid<=ur)
{
update_interval(root<<,nl,mid,ul,mid,val);
update_interval((root<<)+,mid+,nr,mid+,ur,val);
}
tree[root]=max(tree[root<<],tree[(root<<)+]); }
long long query(int root,int nl,int nr,int ul,int ur)
{
if(add[root]!=) push_down(root,nl,nr);
if(nl==ul&&nr==ur)
{
return tree[root];
}
int mid=(nl+nr)>>;
if(ur<=mid)
{
return query(root<<,nl,mid,ul,ur);
}
if(ul>mid)
{
return query((root<<)+,mid+,nr,ul,ur);
}
if(ul<=mid&&mid<=ur)
{
return max(query(root<<,nl,mid,ul,mid),query((root<<)+,mid+,nr,mid+,ur));
} }
void dfs(int now,int pre,long long sum)
{
sum+=w[now];
l[now]=inf;
int son=;
for(int i=;i<edg[now].size();i++)
{
if(pre==edg[now][i]) continue;
son++;
dfs(edg[now][i],now,sum);
int next=edg[now][i];
l[now]=min(l[now],l[next]);
}
r[now]=++index;
val[index]=sum;
if(son==)
{
l[now]=r[now];
}
}
int main()
{
int t;
int cas=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) edg[i].clear();
for(int i=;i<n-;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edg[u].push_back(v);
edg[v].push_back(u);
}
for(int i=;i<n;i++)
scanf("%d",w+i);
index=;
dfs(,,);
/* for(int i=0;i<n;i++)
{
cout<<"i:"<<i<<" "<<l[i]<<" "<<r[i]<<endl;
cout<<val[r[i]]<<endl;
}*/
build(,,n); /*int j=1,t=1;
for(int i=1; i<=(n<<2); i++)
{
j++;
printf("%d ",tree[i]);
if(j>pow(2,(t-1)))
{
printf("\n");
j=1;
t++;
} }
printf("\n\n");*/
printf("Case #%d:\n",cas++);
for(int i=;i<m;i++)
{
char op[]; int tmp1,tmp2;
scanf("%s",op);
if(op[]=='')
{
//cout<<"fuck"<<endl;
int tmp,u;
scanf("%d%d",&tmp,&u);
update_interval(,,n,l[tmp],r[tmp],u-w[tmp]);
w[tmp]=u;
}
else
{
int tmp;
scanf("%d",&tmp);
long long ans = query(,,n,l[tmp],r[tmp]);
printf("%I64d\n",ans);
}
}
}
return ;
}
分析：很显然这个一个树，视作0为根节点。从0号节点到某一节点有且只有一条可达路径。那么每个节点i可以对应一个路径(从0到i这条路径)。对路径通过后序遍历重新编号为1~n.叶子节点所对应区间为[Ki,Kii].Ki为该节点对应的路径的编号。对于非叶子节点对应区间为[Min,Max],Min是该节点所有孩子节点区间左端点中最小的。Max肯定为自身(因为父节点的路径编号要大于孩子节点的路径编号)。那么这个区间的意义是？ 如果一个节点C的区间为[1,3]那么1,2,3这三个编号对应的路径中都经过节点C。并且可以算出每个路径的值也就是说节点0到每个节点的路径长度.NUM[I] 0~i路径的长度。
那么查询操作求经过X节点的最大路径就是X对应的区间[ L[X],R[X] ]中的这些路径对应NUM值的最大值。注意：这里是找一个区间的最大值。
而修改操作让X节点的值改为Y，也就是将X对应区间[ L[X],R[X] ]中这些路径对应的每个NUM值都加上Y-V[X]。(V[X]为原本X节点的价值)。 注意：这里是修改一个区间的值。
所以我们可以看出来，我们可以先用dfs处理，然后用线段树去优化后面的操作。