[TJOI 2015] 旅游 - dydxh - 189735

记录编号	189735	评测结果	AAATTTTTT
题目名称	[TJOI 2015] 旅游	最终得分	33
用户昵称	dydxh	是否通过	未通过
代码语言	C++	运行时间	6.344 s
提交时间	2015-09-29 11:38:37	内存使用	2.27 MiB
显示代码纯文本
/*
Problem:bzoj3107;
Language:c++;
by dydxh;
2015.09.20;
*/
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<utility>
#include<ctime>
#include<cstdlib>
#include<string>
#define ll long long
using namespace std;
const int maxn=50005;
const int oo=1000000000;
const int mod=1000000007;
int n;
int F[maxn],C[maxn][2],V[maxn],Delta[maxn];
int _Max[maxn],_Min[maxn],Max_dif[maxn],Ant_dif[maxn];
bool Rev[maxn];
inline void swap(int &a,int &b){int t=a;a=b,b=t;}
inline int read(){
    int x=0;bool flag=0;char ch=getchar();
    while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return flag?-x:x;
}
bool Is_root(int x){return (C[F[x]][0]!=x && C[F[x]][1]!=x);}
void Update(int x){
	if(!x) return ;
	_Max[x]=_Min[x]=V[x];
	//Max_dif[x]=Min_dif[x]=0;
	Max_dif[x]=Ant_dif[x]=0;
	if(C[x][0]){
		if(_Max[C[x][0]]>_Max[x]) _Max[x]=_Max[C[x][0]];
		if(_Min[C[x][0]]<_Min[x]) _Min[x]=_Min[C[x][0]];
	}
	if(C[x][1]){
		if(_Max[C[x][1]]>_Max[x]) _Max[x]=_Max[C[x][1]];
		if(_Min[C[x][1]]<_Min[x]) _Min[x]=_Min[C[x][1]];
	}
	if(C[x][0]){
		if(Max_dif[C[x][0]]>Max_dif[x])
			Max_dif[x]=Max_dif[C[x][0]];
		if(Ant_dif[C[x][0]]>Ant_dif[x])
			Ant_dif[x]=Ant_dif[C[x][0]];
		if(V[x]-_Min[C[x][0]]>Max_dif[x])
			Max_dif[x]=V[x]-_Min[C[x][0]];
		if(_Max[C[x][0]]-V[x]>Ant_dif[x])
			Ant_dif[x]=_Max[C[x][0]]-V[x];
	}
	if(C[x][1]){
		if(Max_dif[C[x][1]]>Max_dif[x])
			Max_dif[x]=Max_dif[C[x][1]];
		if(Ant_dif[C[x][1]]>Ant_dif[x])
			Ant_dif[x]=Ant_dif[C[x][1]];
		if(_Max[C[x][1]]-V[x]>Max_dif[x])
			Max_dif[x]=_Max[C[x][1]]-V[x];
		if(V[x]-_Min[C[x][1]]>Ant_dif[x])
			Ant_dif[x]=V[x]-_Min[C[x][1]];
	}
	if(C[x][0] && C[x][1]){
		if(_Max[C[x][1]]-_Min[C[x][0]]>Max_dif[x])
			Max_dif[x]=_Max[C[x][1]]-_Min[C[x][0]];
		if(_Max[C[x][0]]-_Min[C[x][1]]>Ant_dif[x])
			Ant_dif[x]=_Max[C[x][0]]-_Min[C[x][1]];
	}
	/*if(C[x][0]){
		if(Max_dif[x]<V[x]-_Min[C[x][0]])
			Max_dif[x]=V[x]-_Min[C[x][0]];
		if(Min_dif[x]>_Min[C[x][0]]-V[x])
			Min_dif[x]=_Min[C[x][0]]-V[x];
		if(Max_dif[x]<Max_dif[C[x][0]])
			Max_dif[x]=Max_dif[C[x][0]];
		if(Min_dif[x]>Min_dif[C[x][0]])
			Min_dif[x]=Min_dif[C[x][0]];
	}
	if(C[x][1]){
		if(Max_dif[x]<_Max[C[x][1]]-V[x])
			Max_dif[x]=_Max[C[x][1]]-V[x];
		if(Min_dif[x]>V[x]-_Max[C[x][1]])
			Min_dif[x]=V[x]-_Max[C[x][1]];
		if(Max_dif[x]<Max_dif[C[x][1]])
			Max_dif[x]=Max_dif[C[x][1]];
		if(Min_dif[x]>Min_dif[C[x][1]])
			Min_dif[x]=Min_dif[C[x][1]];
	}
	if(C[x][0] && C[x][1]){
		if(Max_dif[x]<_Max[C[x][1]]-_Min[C[x][0]])
			Max_dif[x]=_Max[C[x][1]]-_Min[C[x][0]];
		if(Min_dif[x]>_Min[C[x][0]]-_Max[C[x][1]])
			Min_dif[x]=_Min[C[x][0]]-_Max[C[x][1]];
	}*/
}
void Push_Down(int x){
	if(!x) return ;
	if(Rev[x]){
		Rev[x]=0,Rev[C[x][1]]^=1,Rev[C[x][0]]^=1;
		if(C[x][1]){
			swap(C[C[x][1]][1],C[C[x][1]][0]);
			swap(Max_dif[C[x][1]],Ant_dif[C[x][1]]);
		}
		if(C[x][0]){
			swap(C[C[x][0]][1],C[C[x][0]][0]);
			swap(Max_dif[C[x][0]],Ant_dif[C[x][0]]);
		}
		//swap(C[x][1],C[x][0]);
		/*swap(Max_dif[x],Min_dif[x]);
		Max_dif[x]=-Max_dif[x];
		Min_dif[x]=-Min_dif[x];*/
		//swap(Max_dif[x],Ant_dif[x]);
	}
	if(Delta[x]!=0){
		if(C[x][0]){
			Delta[C[x][0]]+=Delta[x];
			V[C[x][0]]+=Delta[x];
			_Max[C[x][0]]+=Delta[x];
			_Min[C[x][0]]+=Delta[x];
		}
		if(C[x][1]){
			Delta[C[x][1]]+=Delta[x];
			V[C[x][1]]+=Delta[x];
			_Max[C[x][1]]+=Delta[x];
			_Min[C[x][1]]+=Delta[x];
		}
		Delta[x]=0;
		/*V[x]+=Delta[x];
		_Max[x]+=Delta[x];
		_Min[x]+=Delta[x];
		Delta[C[x][0]]+=Delta[x];
		Delta[C[x][1]]+=Delta[x];
		Delta[x]=0;*/
	}
}
int Sta[maxn],toper;
void Down_Tag(int x){
	Sta[toper=1]=x;
	while(!Is_root(x)) Sta[++toper]=F[x],x=F[x];
	while(toper) Push_Down(Sta[toper--]);
}
void Rotate(int x,bool aim){
	int p=F[x];
	Push_Down(p),Push_Down(x);
	if(F[p]){
		if(C[F[p]][0]==p) C[F[p]][0]=x;
		else if(C[F[p]][1]==p) C[F[p]][1]=x;
	}
	if(C[x][aim]) F[C[x][aim]]=p;
	C[p][aim^1]=C[x][aim],C[x][aim]=p;
	F[x]=F[p],F[p]=x;
	Update(p),Update(x);
}
void Splay(int x){
	Down_Tag(x);
	while(!Is_root(x)){
		int p=F[x];
		if(Is_root(p)){
			Rotate(x,C[p][0]==x);
			break;
		}
		if(C[F[p]][0]==p){
			if(C[p][0]==x) Rotate(p,1),Rotate(x,1);
			else Rotate(x,0),Rotate(x,1);
		}
		else{
			if(C[p][1]==x) Rotate(p,0),Rotate(x,0);
			else Rotate(x,1),Rotate(x,0);
		}
	}
}
void Access(int x){
	int Last=0;
	while(x){
		Splay(x);
		C[x][1]=Last;
		Update(x);
		Last=x,x=F[x];
	}
}
void Make_root(int x){
	Access(x);
	Splay(x);
	Rev[x]^=1;
	swap(C[x][1],C[x][0]);
	swap(Max_dif[x],Ant_dif[x]);
}
void Connect(int x,int y){
	Make_root(x);
	Access(y);
	Splay(y);
}
void _Link(int x,int y){
	Make_root(x);
	F[x]=y;
}
void _Cut(int x,int y){
	Connect(x,y);
	C[y][0]=F[x]=0;
	Update(y);
}
void New_Pro(){
	n=read();
	for(int i=1;i<=n;i++){
		V[i]=_Max[i]=_Min[i]=read();
		Max_dif[i]=Ant_dif[i]=0;
	}
}
int main(){
    freopen("tjoi2015_travel.in","r",stdin);
    freopen("tjoi2015_travel.out","w",stdout);
	New_Pro();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		_Link(u,v);
	}
	int T=read();
	while(T--){
		int fro=read(),tor=read(),delta=read();
		Connect(fro,tor);
		printf("%d\n",Max_dif[tor]);
		Delta[tor]+=delta;
		V[tor]+=delta,_Max[tor]+=delta,_Min[tor]+=delta;
	}
    return 0;
}