「TJOI2015」旅游 解题报告

「TJOI2015」旅游

LCT沙比题

考虑我们其实是在维护一条链的\(\max\limits_{i<j} v_j-v_i\)

每次直接拿左右子树更新一下就可以了

写的时候把两个方向都维护一下，方便翻转

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

const int N=50010;

using std::min;

using std::max;

#define ls ch[now][0]

#define rs ch[now][1]

#define fa par[now]

int res[N],tag[N],ansl[N],ansr[N],ch[N][2],par[N],mx[N],mi[N],dat[N],s[N],tot;

int identity(int now){return ch[fa][1]==now;}

bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}

void connect(int f,int now,int typ){ch[fa=f][typ]=now;}

void updata(int now)

{

	ansl[now]=max(max(ansl[ls],ansl[rs]),max(mx[rs],dat[now])-min(mi[ls],dat[now]));

	ansr[now]=max(max(ansr[ls],ansr[rs]),max(mx[ls],dat[now])-min(mi[rs],dat[now]));

	mx[now]=max(max(mx[ls],mx[rs]),dat[now]);

	mi[now]=min(min(mi[ls],mi[rs]),dat[now]);

}

void Reverse(int now)

{

	res[now]^=1;

	std::swap(ls,rs);

	std::swap(ansl[now],ansr[now]);

}

void pushdown(int now)

{

	if(tag[now])

	{

		if(ls) tag[ls]+=tag[now],mx[ls]+=tag[now],mi[ls]+=tag[now],dat[ls]+=tag[now];

		if(rs) tag[rs]+=tag[now],mx[rs]+=tag[now],mi[rs]+=tag[now],dat[rs]+=tag[now];

		tag[now]=0;

	}

	if(res[now])

	{

		if(ls) Reverse(ls);

		if(rs) Reverse(rs);

		res[now]=0;

	}

}

void Rotate(int now)

{

	int p=fa,typ=identity(now);

	connect(p,ch[now][typ^1],typ);

	if(isroot(p)) connect(par[p],now,identity(p));

	else fa=par[p];

	connect(now,p,typ^1);

	updata(p),updata(now);

}

void splay(int now)

{

	while(isroot(now)) s[++tot]=now,now=fa;

	s[++tot]=now;

	while(tot) pushdown(s[tot--]);

	now=s[1];

	for(;isroot(now);Rotate(now))

		if(isroot(fa))

			Rotate(identity(now)^identity(fa)?now:fa);

}

void access(int now)

{

	for(int las=0;now;las=now,now=fa)

		splay(now),rs=las,updata(now);

}

void evert(int now){access(now),splay(now),Reverse(now);}

void split(int u,int v)

{

    evert(u);

    access(v);

    splay(v);

}

void modi(int now,int d){tag[now]+=d,dat[now]+=d,mx[now]+=d,mi[now]+=d;}

int query(int u,int v,int d)

{

    split(u,v);

    modi(v,d);

    return ansl[v];

}

int head[N],to[N<<1],Next[N<<1],cnt;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

void dfs(int now)

{

	for(int v,i=head[now];i;i=Next[i])

		if((v=to[i])!=fa)

			par[v]=now,dfs(v);

}

int main()

{

    int n,q;

	read(n);

	mi[0]=1<<30;

	for(int i=1;i<=n;i++) read(dat[i]),mx[i]=mi[i]=dat[i];

	for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);

	dfs(1);

	read(q);

	for(int a,b,d,i=1;i<=q;i++)

	{

		read(a),read(b),read(d);

		printf("%d\n",query(a,b,d));

	}

	return 0;

}

---

2019.2.24