[TJOI2015]旅游

问题描述

为了提高智商，ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可以互达。每座城市都有一种宝石，有一定的价格。ZJY为了赚取最高利益，她会选择从A城市买入再转手卖到B城市。由于ZJY买宝石时经常卖萌，因而凡是ZJY路过的城市，这座城市的宝石价格会上涨。让我们来算算ZJY旅游完之后能够赚取的最大利润。（如a城市宝石价格为v，则ZJY出售价格也为v）

输入格式

第一行输入一个正整数N，表示城市个数。

接下来一行输入N个正整数表示每座城市宝石的最初价格p，每个宝石的初始价格不超过100。

第三行开始连续输入N-1行，每行有两个数字x和y。表示x城市和y城市有一条路径。城市编号从1开始。

下一行输入一个整数Q，表示询问次数。

接下来Q行，每行输入三个正整数a,b,v，表示ZJY从a旅游到b，城市宝石上涨v。

即是询问a—>b(有方向)间路径上的max(Price[j]−Price[i])) 且j到a的距离比i到a大。然后把这条路径上所有点的点权+v。

1≤ N≤50000， 1≤Q ≤50000

输出格式

对于每次询问，输出ZJY可能获得的最大利润，如果亏本则输出0。

样例输入

3

1 2 3

1 2

2 3

2

1 2 100

1 3 100

样例输出

1

1

显然的树链剖分，主要处理询问。

考虑用线段树维护，线段树上记录$Max，Min，Lans，Rans$，其中$Lans=max(Max[ls]-Min[rs],Lans[ls],Lans[rs])$。

$Rans$同理，然后每次查询可以用一个结构体来保存结果，将询问拆到线段树整区间上再向上合并即可。

最后求结果的时候，先找出$a,b$的$lca$，然后答案就是$a\rightarrow lca$的$Lans$，$lca\rightarrow b$的$Rans$，$lca\rightarrow b$的$Max$减去$a\rightarrow lca$的$Min$三者的最大值。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 50005
#define M 200005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,q,A[N],B[N];
int TOT,LA[N],EN[N<<1],NE[N<<1];
int fa[N],dep[N],top[N],id[N],son[N],si[N],VT;
struct node
{
	int Max,Min,Ans;
	node(int a=0,int b=1e9,int c=0)
	{Max=a;Min=b;Ans=c;}
};
node Merge(node a,node b)
{
	node c;
	c.Max=max(a.Max,b.Max);
	c.Min=min(a.Min,b.Min);
	c.Ans=max(a.Max-b.Min,max(a.Ans,b.Ans));
	return c;
}
namespace Seg
{
	int tot,ls[M],rs[M],Max[M],Min[M],Lmax[M],Rmax[M],lazy[M];
	void MT(int p)
	{
		int l=ls[p],r=rs[p];
		Max[p]=max(Max[l],Max[r]);
		Min[p]=min(Min[l],Min[r]);
		Lmax[p]=max(Max[l]-Min[r],max(Lmax[l],Lmax[r]));
		Rmax[p]=max(Max[r]-Min[l],max(Rmax[l],Rmax[r]));
	}
	void PD(int p)
	{
		Max[ls[p]]+=lazy[p];
		Max[rs[p]]+=lazy[p];
		Min[ls[p]]+=lazy[p];
		Min[rs[p]]+=lazy[p];
		lazy[ls[p]]+=lazy[p];
		lazy[rs[p]]+=lazy[p];
		lazy[p]=0;
	}
	int BT(int x,int y)
	{
		int p=++tot;
		if(x==y)return Max[p]=Min[p]=B[x],p;
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
		return MT(p),p;
	}
	void ADD(int p,int l,int r,int x,int y,int d)
	{
		if(lazy[p])PD(p);
		if(x<=l&&y>=r){Max[p]+=d;Min[p]+=d;lazy[p]+=d;return;}
		int mid=l+r>>1;
		if(x<=mid&&y>=l)ADD(ls[p],l,mid,x,y,d);
		if(x<=r&&y>mid)ADD(rs[p],mid+1,r,x,y,d);
		MT(p);
	}
	node Glmax(int p,int l,int r,int x,int y)
	{
		if(lazy[p])PD(p);
		if(x<=l&&y>=r)return node(Max[p],Min[p],Lmax[p]);
		int mid=l+r>>1;node Lp,Rp;
		if(x<=mid&&y>=l)Lp=Glmax(ls[p],l,mid,x,y);
		if(x<=r&&y>mid)Rp=Glmax(rs[p],mid+1,r,x,y);
		return Merge(Lp,Rp);
	}
	node Grmax(int p,int l,int r,int x,int y)
	{
		if(lazy[p])PD(p);
		if(x<=l&&y>=r)return node(Max[p],Min[p],Rmax[p]);
		int mid=l+r>>1;node Lp,Rp;
		if(x<=mid&&y>=l)Lp=Grmax(ls[p],l,mid,x,y);
		if(x<=r&&y>mid)Rp=Grmax(rs[p],mid+1,r,x,y);
		return Merge(Rp,Lp);
	}
}
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void FHE(int x,int f)
{
	int i,y;
	dep[x]=dep[f]+1;
	fa[x]=f;
	si[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(y==f)continue;
		FHE(y,x);si[x]+=si[y];
		if(si[y]>si[son[x]])son[x]=y;
	}
}
void CHE(int x,int f)
{
	int i,y;
	top[x]=f;
	id[x]=++VT;
	B[VT]=A[x];
	if(son[x])CHE(son[x],f);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(y==fa[x])continue;
		if(y!=son[x])CHE(y,y);
	}
}
int LCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	return y;
}
void MD(int x,int y,int d)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		Seg::ADD(1,1,n,id[top[x]],id[x],d);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	Seg::ADD(1,1,n,id[y],id[x],d);
}
int Gans(int x,int y)
{
	int lca=LCA(x,y);node L,R;
	while(top[x]!=top[lca])
	{
		L=Merge(Seg::Glmax(1,1,n,id[top[x]],id[x]),L);
		x=fa[top[x]];
	}
	L=Merge(Seg::Glmax(1,1,n,id[lca],id[x]),L);
	while(top[y]!=top[lca])
	{
		R=Merge(R,Seg::Grmax(1,1,n,id[top[y]],id[y]));
		y=fa[top[y]];
	}
	R=Merge(R,Seg::Grmax(1,1,n,id[lca],id[y]));
	return max(R.Max-L.Min,max(L.Ans,R.Ans));
}
int main_main()
{
	int i,j,k,x,y,z;
	_R(n);
	for(i=1;i<=n;i++)_R(A[i]);
	for(i=1;i<n;i++)
	{
		_R(x);_R(y);
		ADD(x,y);ADD(y,x);
	}
	FHE(1,0);CHE(1,1);Seg::BT(1,n);
	_R(q);
	for(i=1;i<=q;i++)
	{
		_R(x);_R(y);_R(z);
		printf("%d\n",Gans(x,y));
		MD(x,y,z);
	}
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}