- #pragmacomment(linker, "/STACK:1024000000,1024000000")
- #include
- #include
- #include
- #include
- #include<string>
- #include
- #include
- #include
- #include
- using namespace std;
- #definell __int64#defineMAXN 100010#defineinf 1000000000000int head[MAXN];
- struct edg
- {
- int to,next;
- }edge[MAXN*2];
- int cnt,num;
- ll w[MAXN],dis[MAXN],ls[MAXN],rs[MAXN],ind[MAXN];
- voidadd(intu,int v)
- {
- edge[cnt].to=v;
- edge[cnt].next=head[u];
- head[u]=cnt++;
- }
- struct node
- {
- int l,r;
- ll w,lz;
- }tree[MAXN<<2];
- voiddfs(intu,int fa)
- {
- num++;
- ls[u]=num;
- ind[num]=u;
- for(inti=head[u];i!=-1;i=edge[i].next)
- {
- intv=edge[i].to;
- if(v==fa)
- continue;
- dis[v]=dis[u]+w[v];
- dfs(v,u);
- }
- rs[u]=num;
- }
- voidPush_down(int a)
- {
- tree[a<<1].lz+=tree[a].lz;
- tree[a<<1].w+=tree[a].lz;
- tree[a<<1|1].lz+=tree[a].lz;
- tree[a<<1|1].w+=tree[a].lz;
- tree[a].lz=0;
- }
- voidPush_up(int a)
- {
- tree[a].w=max(tree[a<<1].w,tree[a<<1|1].w);
- }
- voidBuild(intl,intr,int a)
- {
- tree[a].l=l;
- tree[a].r=r;
- tree[a].lz=0;
- if(l==r)
- {
- tree[a].w=dis[ind[l]];
- return ;
- }
- intmid=(l+r)>>1;
- Build(l,mid,a<<1);
- Build(mid+1,r,a<<1|1);
- Push_up(a);
- }
- voidUpdate(intl,intr,intl1,intr1,ll w1,int a)
- {
- if(l1<=l&&r<=r1)
- {
- tree[a].w+=w1;
- tree[a].lz+=w1;
- return ;
- }
- intmid=(l+r)>>1;
- if(tree[a].lz)
- Push_down(a);
- if(l1<=mid)
- Update(l,mid,l1,r1,w1,a<<1);
- if(r1>mid)
- Update(mid+1,r,l1,r1,w1,a<<1|1);
- Push_up(a);
- }
- ll Ques(intl,intr,intl1,intr1,int a)
- {
- ll mx=-inf;
- if(l1<=l&&r<=r1)
- {
- return tree[a].w;
- }
- intmid=(l+r)>>1;
- if(tree[a].lz)
- Push_down(a);
- if(l1<=mid)
- mx=max(mx,Ques(l,mid,l1,r1,a<<1));
- if(r1>mid)
- mx=max(mx,Ques(mid+1,r,l1,r1,a<<1|1));
- return mx;
- }
- int main()
- {
- int t,ca;
- ca=1;
- scanf("%d",&t);
- while(t--)
- {
- int n,m;
- scanf("%d%d",&n,&m);
- memset(head,-1,sizeof(head));
- cnt=0;
- for(inti=1;i)
- {
- int a,b;
- scanf("%d%d",&a,&b);
- add(a,b);
- add(b,a);
- }
- for(inti=0;i)
- scanf("%I64d",&w[i]);
- num=0;
- dis[0]=w[0];
- dfs(0,-1);
- Build(1,num,1);
- printf("Case #%d:\n",ca++);
- while(m--)
- {
- int way;
- scanf("%d",&way);
- if(way==1)
- {
- int a;
- scanf("%I64d",&a);
- printf("%I64d\n",Ques(1,n,ls[a],rs[a],1));
- }
- else
- {
- int a;
- ll b;
- scanf("%d%I64d",&a,&b);
- Update(1,n,ls[a],rs[a],b-w[a],1);
- w[a]=b;
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1989386.html