题面

百度科技园内有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( \left|\ v\ \right|<100000)$。

接下来m行，有两种操作：0 x y，表示编号为x的零食机的价值变为y；1 x，表示询问从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。

本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：

#pragma comment(linker, "/STACK:1024000000,1024000000") Output 对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。

对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。

代码（TLE）

树链剖分+线段树维护

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>
//#include<cstdio>
//#include<algorithm>
//#include<cstring>
//#ifdef ONLINE_JUDGE
//
//#endif
#define lson o<<1
#define rson o<<1|1
#define nmid int mid=(nowl+nowr)>>1
using namespace std;
typedef long long ll;
const int maxn=100005;

inline int read(){
	int op=1,res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') op=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-48;
		ch=getchar();
	}
	return res*op;
}

int n,m;

struct Edge{
	int _this,nxt;
	Edge(){
		_this=nxt=0;
	}
}edge[maxn<<1];
int headnxt[maxn],idx;
inline void merge(int from,int to){
	edge[++idx]._this=to;
	edge[idx].nxt=headnxt[from];
	headnxt[from]=idx;
}
ll v[maxn];

bool vis[maxn];
//int fa[maxn];
int id[maxn],tim=1;
ll qzh[maxn];
int tree_end[maxn];
int siz[maxn],maxson[maxn];
void dfs1(int f){
	int mxsiz=0;
	for(int it=headnxt[f];it;it=edge[it].nxt){
		int nowtry=edge[it]._this;
		if(!vis[nowtry]){
			vis[nowtry]=1;
			dfs1(nowtry);
			vis[nowtry]=0;
			siz[f]+=siz[nowtry];
			if(siz[nowtry]>mxsiz){
				maxson[f]=nowtry;
				mxsiz=siz[nowtry];
			}
		}
	}
	++siz[f];
}

void dfs2(int f,int fa){
	qzh[id[f]]=qzh[id[fa]]+v[f];
	tree_end[id[f]]=id[f];
	
	
	int mson=maxson[f];
	if(!mson) return;
	vis[mson]=1;
	id[mson]=++tim;
//	fa[id[mson]]=id[f];
	
	dfs2(mson,f);
	vis[mson]=0;
	tree_end[id[f]]=max(id[f],tree_end[id[mson]]);
	
	
	for(int it=headnxt[f];it;it=edge[it].nxt){
		int nowtry=edge[it]._this;
		if(!vis[nowtry]&&nowtry!=mson){
			vis[nowtry]=1;
			id[nowtry]=++tim;
//			fa[id[nowtry]]=id[f];
			
			dfs2(nowtry,f);
			vis[nowtry]=0;
			tree_end[id[f]]=max(tree_end[id[f]],tree_end[id[nowtry]]);
		}
	}
}

ll t[maxn<<2],lazy[maxn<<2];
inline void push_up(int o){
	t[o]=max(t[lson],t[rson]);
}
inline void push_down(int o){
	if(!lazy[o]) return;
	t[lson]+=lazy[o];
	t[rson]+=lazy[o];
	lazy[lson]=lazy[o];
	lazy[rson]=lazy[o];
	lazy[o]=0;
}
void build(int nowl,int nowr,int o){
	lazy[o]=0;
	if(nowl==nowr){
		t[o]=qzh[nowl];
		return;
	}
	nmid;
	build(nowl,mid,lson);
	build(mid+1,nowr,rson);
	push_up(o);
}

ll query(int nowl,int nowr,int l,int r,int o){
	if(l<=nowl&&nowr<=r){
		return t[o];
	}
	nmid;
	push_down(o);
	ll res=-(1e18);
	if(l<=mid) res=max(res,query(nowl,mid,l,r,lson));
	if(r>mid) res=max(res,query(mid+1,nowr,l,r,rson));
	return res;
}

void update(int nowl,int nowr,int l,int r,int o,ll val){
	if(l<=nowl&&nowr<=r){
		t[o]+=val;
		lazy[o]=val;
		return;
	}
	nmid;
	push_down(o);
	if(l<=mid) update(nowl,mid,l,r,lson,val);
	if(r>mid) update(mid+1,nowr,l,r,rson,val);
	push_up(o);
}

int i;

inline void init(){
	memset(headnxt,0,sizeof headnxt);
	memset(v,0,sizeof v);
	memset(vis,0,sizeof vis);
	memset(id,0,sizeof id);
	memset(qzh,0,sizeof qzh);
	memset(tree_end,0,sizeof tree_end);
	memset(siz,0,sizeof siz);
	memset(maxson,0,sizeof maxson);
	idx=0;
	tim=1;
//	for(int i=1;i<=n;++i) {
//		v[i]=0;
//		vis[i]=0;
//		fa[i]=0;
//		id[i]=0;
//		qzh[i]=0;
//		tree_end[i]=0;
//		siz[i]=0;
//		maxson[i]=0;
//	}
//	memset(siz,0,sizeof siz);
//	memset(maxson,0,sizeof maxson);
}

int main(){
	
//	freopen("a.in","r",stdin);
	int _=read();
	for(int T=1;T<=_;++T){
		printf("Case #%d:\n",T);
		n=read();m=read();	
		
		int s,t;
		for(i=1;i<n;++i){
			s=read();t=read();
			++s;++t;
			merge(s,t);
			merge(t,s);
		}
		for(i=1;i<=n;++i){
			v[i]=read();
		}
		vis[1]=1;
		id[1]=1;
//		fa[1]=0;
		qzh[1]=v[1];
		dfs1(1);
		dfs2(1,0);
//		for(ll i=1;i<=n;++i) cout<<tree_end[i]<<" ";
		build(1,n,1);
		int op,x;
		ll ch;
		while(m--){
			op=read();//
			if(op==1){
				x=read();
				x=id[x+1];
				printf("%lld\n",query(1,n,x,tree_end[x],1));
			}
			else{
				x=read();ch=read();
				x=x+1;
				update(1,n,id[x],tree_end[id[x]],1,ch-v[x]);
				v[x]=ch;
			}
		}
	}
    return 0;
}

求调 qwq