Yaoge’s maximum profit

1
5
1
2
3
4
5
1 2
2 3
3 4
4 5
5
1 5 1
5 1 1
1 1 2
5 1 1
1 2 1

4
0
0
1
0

路径大值与小值差值的最大值，其中满足小值在大值前面出现，加入求u->:v的路径上答案，可以先u->make_root(），然后v->access(),然后输出答案就可以了。

代码：

‘

/* ***********************************************
Author :rabbit
Created Time :2014/11/2 19:01:37
File Name :4.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=100100;
struct Node *null;
struct Node{
	Node *ch[2],*fa;
	int Max,Min,mm,rmm,rev,add,val;
	inline void clear(int _val){
		fa=ch[0]=ch[1]=null;
		Max=Min=val=_val;
		rev=add=mm=rmm=0;
	}
	inline void push_up(){
		if(this==null)return;
		mm=0;
		mm=max(mm,ch[0]->mm);
		mm=max(mm,ch[1]->mm);
		mm=max(mm,max(val,ch[1]->Max)-ch[0]->Min);
		mm=max(mm,ch[1]->Max-min(val,ch[0]->Min));
		rmm=0;
		rmm=max(rmm,ch[0]->rmm);
		rmm=max(rmm,ch[1]->rmm);
		rmm=max(rmm,max(val,ch[0]->Max)-ch[1]->Min);
		rmm=max(rmm,ch[0]->Max-min(val,ch[1]->Min));
		Max=max(val,max(ch[0]->Max,ch[1]->Max));
		Min=min(val,min(ch[0]->Min,ch[1]->Min));
	}
	inline void setc(Node *p,int d){
		ch[d]=p;
		p->fa=this;
	}
	inline bool d(){
		return fa->ch[1]==this;
	}
	inline bool isroot(){
		return fa==null||fa->ch[0]!=this&&fa->ch[1]!=this;
	}
	inline void flip(){
		if(this==null)return;
		swap(ch[0],ch[1]);
		rev^=1;
		swap(mm,rmm);
	}
	inline void update_add(int w){
		if(this==null)return;
		Max+=w;
		Min+=w;
		val+=w;
		add+=w;
	}
	inline void push_down(){
		if(add){
			ch[0]->update_add(add);
			ch[1]->update_add(add);
			add=0;
		}
		if(rev){
			ch[0]->flip();
			ch[1]->flip();
			rev=0;
		}
	}
    inline void go(){
		if(!isroot())fa->go();
		push_down();
	}
	inline void rot(){
		Node *f=fa,*ff=fa->fa;
		int c=d(),cc=fa->d();
		f->setc(ch[!c],c);
		this->setc(f,!c);
		if(ff->ch[cc]==f)ff->setc(this,cc);
		else  this->fa=ff;
		f->push_up();
	}
	inline Node *splay(){
		go();
		while(!isroot()){
			if(!fa->isroot())
				d()==fa->d()?fa->rot():rot();
			rot();
		}
		push_up();
		return this;
	}
	inline Node *access(){
		for(Node *p=this,*q=null;p!=null;q=p,p=p->fa){
			p->splay()->setc(q,1);
			p->push_up();
		}
		return splay();
	}
	inline Node *find_root(){
		Node *x;
		for(x=access();x->push_down(),x->ch[0]!=null;x=x->ch[0]);
		return x;
	}
	void make_root(){
		access()->flip();
	}
};
Node pool[maxn],*tail;
Node*node[maxn];
struct Edge{
	int next,to;
}edge[maxn*2];
int head[maxn],tol;
inline void addedge(int u,int v){
	edge[tol].to=v;
	edge[tol].next=head[u];
	head[u]=tol++;
}
void dfs(int u,int pre){
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==pre)continue;
		node[v]->fa=node[u];
		dfs(v,u);
	}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,m,T;
	 scanf("%d",&T);
	 while(T--){
		 scanf("%d",&n);
		 tail=pool;
		 null=tail++;
		 null->val=null->mm=null->rmm=0;
		 null->Max=-INF;null->Min=INF;
		 null->ch[0]=null->ch[1]=null->fa=null;
		 null->add=null->rev=0;
		 for(int i=1;i<=n;i++){
			 int w;
			 scanf("%d",&w);
			 node[i]=tail++;
			 node[i]->clear(w);
		 }
		 memset(head,-1,sizeof(head));tol=0;
		 for(int i=1;i<n;i++){
			 int u,v;
			 scanf("%d%d",&u,&v);
			 addedge(u,v);
			 addedge(v,u);
		 }
		 dfs(1,1);
		 scanf("%d",&m);
		 while(m--){
			 int u,v,d;
			 scanf("%d%d%d",&u,&v,&d);
			 node[u]->make_root();
			 node[v]->access();
			 printf("%d\n",node[v]->mm);
			 node[v]->update_add(d);
		 }
	 }
     return 0;
}

HDU 5052 LCT

原文：http://blog.csdn.net/xianxingwuguan1/article/details/40713387