记录编号	373764	评测结果	AAAAAAAAAAA
题目名称	[河南省队2016]无根树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.975 s
提交时间	2017-02-21 19:05:27	内存使用	65.16 MiB

#include<cstdio>
#include<queue>
using namespace std;
const int N=1e6+10;
int max(int x,int y){return x>y?x:y;}
struct edge{int f,t;}w[N];
int n,m,v[N],head[N],tail[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=(edge){f,t};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
}
int ans[4];
struct Segment_Tree{
	int v[N],best[N],bl[N],br[N],sum[N];
	#define lc x<<1
	#define rc x<<1|1
	void update(int x){
		sum[x]=sum[lc]+sum[rc];
		best[x]=max(br[lc]+bl[rc],max(best[lc],best[rc]));
		bl[x]=max(bl[lc],sum[lc]+bl[rc]);
		br[x]=max(br[rc],sum[rc]+br[lc]);
	}
	void change(int p,int d){
		int x=1,l=1,r=n;
		while (l<r){
			int mid=(l+r)>>1;
			if (p>mid) l=mid+1,x=rc;else r=mid,x=lc;
		}
		sum[x]+=d;v[l]+=d;
		best[x]=bl[x]=br[x]=max(v[l],0);
		for (x>>=1;x;x>>=1) update(x);
	}
	void getmax(int x,int l,int r,int L,int R,int *ans){
		if (l>=L&&r<=R){
			ans[0]=sum[x];
			ans[1]=bl[x];ans[2]=br[x];
			ans[3]=best[x];
			return;
		}
		int mid=(l+r)>>1,al[4]={0},ar[4]={0};
		if (R>mid) getmax(rc,mid+1,r,L,R,ar);
		if (L<=mid) getmax(lc,l,mid,L,R,al);
		ans[0]=al[0]+ar[0];
		ans[1]=max(al[1],al[0]+ar[1]);
		ans[2]=max(ar[2],ar[0]+al[2]);
		ans[3]=max(al[2]+ar[1],max(al[3],ar[3]));
	}
}T;
int fa[N],big[N],s[N],dfn[N],link[N],Right[N];
void dfs(int x){
	s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		fa[w[i].t]=x;
		dfs(w[i].t);
		s[x]+=s[w[i].t];
		if (s[big[x]]<s[w[i].t]) big[x]=w[i].t;
	}
}
void po(int x){
	static int cnt=0;
	dfn[x]=++cnt;
	link[x]=dfn[x]==dfn[fa[x]]+1?link[fa[x]]:x;
	Right[link[x]]=dfn[x];
	if (!big[x]) return;
	po(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i].t!=fa[x]&&w[i].t!=big[x]) po(w[i].t);
}
struct heap{
	priority_queue<int> Q1,Q2;
	void push(int x){Q1.push(x);}
	void del(int x){Q2.push(x);}
	int top(){
		while (!Q2.empty()&&Q1.top()==Q2.top()) Q1.pop(),Q2.pop();
		return Q1.top();
	}
}H;
void cval(int p,int d){
	while (p){
		int top=link[p];
		T.getmax(1,1,n,dfn[top],Right[top],ans);
		int last=ans[1];
		H.del(ans[3]);
		T.change(dfn[p],d);
		T.getmax(1,1,n,dfn[top],Right[top],ans);
		p=fa[top];d=ans[1]-last;
		H.push(ans[3]);
	}
}
int main()
{
	freopen("nortree.in","r",stdin);
	freopen("nortree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&v[i]);
	for (int i=1,f,t;i<n;i++){
		scanf("%d%d",&f,&t);
		add(f,t);add(t,f);
	}
	fa[1]=1;dfs(1);po(1);fa[1]=0;
	for (int i=1;i<=n;i++) H.push(0);
	for (int i=1;i<=n;i++) cval(i,v[i]);
	int tp,x,y;
	while (m--){
		scanf("%d",&tp);
		if (tp==1){
			scanf("%d%d",&x,&y);
			cval(x,y-v[x]);
			v[x]=y;
		}
		else printf("%d\n",H.top());
	}
	return 0;
}