记录编号	162149	评测结果	AAAAAAAAA
题目名称	[TJOI 2015] 旅游	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.216 s
提交时间	2015-05-14 15:06:57	内存使用	6.47 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int INF=1000000000;
#define Nil NULL
int log_2(int x){
	int ans=-1;
	while(x){
		ans++;
		x>>=1;
	}
	return ans;
}
const int SIZEN=50010;
int N;
vector<int> c[SIZEN];
int value[SIZEN]={0};
void Read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&value[i]);
	int a,b;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
}
class Data{
public:
	int fmx,bmx;//fmx:后-前,bmx:前-后 
	int mx,mn;
	void Assign_One(int v){
		fmx=bmx=0;
		mx=mn=v;
	}
	void operator = (int v){
		Assign_One(v);
	}
	bool Empty(void)const{
		return mn==INF;
	}
	void Add(int v){
		mx+=v;
		mn+=v;
	}
	Data(int fmx_,int bmx_,int mx_,int mn_){
		fmx=fmx_;
		bmx=bmx_;
		mx=mx_;
		mn=mn_;
	}
	Data(int v){Assign_One(v);}
	Data(){
		fmx=bmx=-INF;
		mx=-INF;mn=INF;
	}
};
void print(Data d){
	cout<<"("<<d.fmx<<" "<<d.bmx<<" "<<d.mx<<" "<<d.mn<<")"<<endl;
}
Data Reverse(const Data &d){
	return Data(d.bmx,d.fmx,d.mx,d.mn);
}
Data operator + (const Data &d1,const Data &d2){
	if(d1.Empty()) return d2;
	if(d2.Empty()) return d1;
	Data d;
	d.fmx=max(d1.fmx,d2.fmx);
	d.fmx=max(d.fmx,d2.mx-d1.mn);
	d.bmx=max(d1.bmx,d2.bmx);
	d.bmx=max(d.bmx,d1.mx-d2.mn);
	d.mx=max(d1.mx,d2.mx);
	d.mn=min(d1.mn,d2.mn);
	return d;
}
class Node{
public:
	int l,r;
	Node *lc,*rc;
	Data key;
	int lazy;
	int id;
	Node(){
		lc=rc=Nil;
		lazy=0;
	}
	void Add(int v){
		key.Add(v);
		lazy+=v;
	}
	void Push_Down(void){
		if(lazy&&lc!=Nil){
			lc->Add(lazy);
			rc->Add(lazy);
			lazy=0;
		}
	}
	void Push_Up(void){
		if(lc!=Nil){
			key=lc->key+rc->key;
		}
	}
	int Query_Id(int a){
		Push_Down();
		if(l>a||r<a) return 0;
		if(l==a&&r==a) return id;
		else return lc->Query_Id(a)+rc->Query_Id(a);
	}
	Data Query(int a,int b){
		Push_Down();
		if(l>b||r<a) return Data();
		if(l>=a&&r<=b) return key;
		else return lc->Query(a,b)+rc->Query(a,b);
	}
	void Modify(int a,int b,int v){
		Push_Down();
		if(l>b||r<a) return;
		if(l>=a&&r<=b) Add(v);
		else{
			lc->Modify(a,b,v);
			rc->Modify(a,b,v);
			Push_Up();
		}
	}
};
Node *Build(int a,int b,int val[],int ids[]){
	Node *p=new Node();
	p->l=a,p->r=b;
	if(a==b){
		p->key=val[a];
		p->id=ids[a];
	}
	else{
		int mid=(a+b)/2;
		p->lc=Build(a,mid,val,ids);
		p->rc=Build(mid+1,b,val,ids);
		p->Push_Up();
	}
	return p;
}
int father[SIZEN][21]={0};
int height[SIZEN]={0};
int depth[SIZEN]={0};
int belong[SIZEN]={0};
int top[SIZEN]={0};
bool is_leaf[SIZEN]={0};
Node *root[SIZEN];
int Get_LCA(int a,int b){
	if(depth[a]<depth[b]) swap(a,b);
	int mx=log_2(N);
	for(int i=mx;i>=0;i--){
		if(depth[father[a][i]]>=depth[b]) a=father[a][i];
	}
	if(a==b) return a;
	for(int i=mx;i>=0;i--){
		if(father[a][i]!=father[b][i]){
			a=father[a][i];
			b=father[b][i];
		}
	}
	return father[a][0];
}
int Work(int a,int b,int v){
	bool inv=false;
	if(depth[a]<depth[b]) swap(a,b),inv=true;
	Data ansl,ansr;
	while(depth[a]>depth[b]){
		int d=max(depth[top[a]],depth[b]+1);
		ansl=ansl+Reverse(root[a]->Query(d,depth[a]));
		root[a]->Modify(d,depth[a],v);
		a=root[a]->Query_Id(d);
		a=father[a][0];
	}
	while(a!=b){
		int d=max(depth[top[a]],depth[top[b]]);
		ansl=ansl+Reverse(root[a]->Query(d,depth[a]));
		root[a]->Modify(d,depth[a],v);
		ansr=root[b]->Query(d,depth[b])+ansr;
		root[b]->Modify(d,depth[b],v);
		a=root[a]->Query_Id(d);
		b=root[b]->Query_Id(d);
		a=father[a][0];
		b=father[b][0];
	}
	ansl=ansl+Reverse(root[a]->Query(depth[a],depth[a]));
	root[a]->Modify(depth[a],depth[a],v);
	Data ans=ansl+ansr;
	if(inv) ans=Reverse(ans);
	int gain=max(ans.fmx,0);
	printf("%d\n",gain);
}
void Make_Tree(int x){
	depth[x]=depth[father[x][0]]+1;
	is_leaf[x]=true;
	belong[x]=x;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(u==father[x][0]) continue;
		is_leaf[x]=false;
		father[u][0]=x;
		Make_Tree(u);
		if(height[u]>=height[x]){
			height[x]=height[u];
			belong[x]=belong[u];
		}
	}
	height[x]++;
	top[belong[x]]=x;
}
int chain_val[SIZEN]={0};
int chain_id[SIZEN]={0};
void Prepare(void){
	Make_Tree(1);
	int mx=log_2(N);
	for(int j=1;j<=mx;j++){
		for(int i=1;i<=N;i++){
			father[i][j]=father[father[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=N;i++){
		if(!is_leaf[i]) continue;
		int x=i;
		while(x!=top[i]){
			chain_val[depth[x]]=value[x];
			chain_id[depth[x]]=x;
			x=father[x][0];
		}
		chain_val[depth[x]]=value[x];
		chain_id[depth[x]]=x;
		root[i]=Build(depth[top[i]],depth[i],chain_val,chain_id);
	}
	for(int i=1;i<=N;i++){
		top[i]=top[belong[i]];
		root[i]=root[belong[i]];
	}
}
int main(){
	freopen("tjoi2015_travel.in","r",stdin);
	freopen("tjoi2015_travel.out","w",stdout);
	Read();
	Prepare();
	int M,a,b,v;
	scanf("%d",&M);
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&a,&b,&v);
		Work(a,b,v);
	}
	return 0;
}