Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## splay 解出来了，但是速度慢，1700ms+

Posted by hz_cool at 2017-03-09 14:46:07 on Problem 3728
```代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <set>

using namespace std;
const int maxn=5e4+5;
int fa[maxn],ch[maxn][2],rev[maxn],Min[maxn],Max[maxn],d1[maxn],d2[maxn],n,val[maxn],sta[maxn],top=0;
int getlc(int x)
{
return ch[fa[x]][1]==x;
}
bool isroot(int x)
{
return fa[x]==0||(ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);
}
void merge(int x,int y,int w)
{
ch[x][w]=y;
fa[y]=x;
}
void update(int x)
{
Min[x]=Max[x]=val[x];
int t1=0,t2=0,t3=0,t4=0;
if(ch[x][0])
{
Min[x]=min(Min[x],Min[ch[x][0]]);
Max[x]=max(Max[x],Max[ch[x][0]]);
t1=max(d1[ch[x][0]],val[x]-Min[ch[x][0]]);
t3=max(d2[ch[x][0]],Max[ch[x][0]]-val[x]);
}
if(ch[x][1])
{
Min[x]=min(Min[x],Min[ch[x][1]]);
Max[x]=max(Max[x],Max[ch[x][1]]);
t2=max(d1[ch[x][1]],Max[ch[x][1]]-val[x]);
t4=max(d2[ch[x][1]],val[x]-Min[ch[x][1]]);
}
d1[x]=max(t1,t2);
d2[x]=max(t3,t4);
if(ch[x][0]&&ch[x][1])
{
d1[x]=max(d1[x],Max[ch[x][1]]-Min[ch[x][0]]);
d2[x]=max(d2[x],Max[ch[x][0]]-Min[ch[x][1]]);
}
}
void push_down(int x)
{
if(!rev[x]) return;
swap(ch[x][0],ch[x][1]);
swap(d1[ch[x][0]],d2[ch[x][0]]);
swap(d1[ch[x][1]],d2[ch[x][1]]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
void rot(int x,int w)
{
int z=fa[fa[x]];
if(!isroot(fa[x])) ch[z][getlc(fa[x])]=x;
merge(fa[x],ch[x][w^1],w);
merge(x,fa[x],w^1);
update(fa[x]);
fa[x]=z;
}
void splay(int x)
{
sta[++top]=x;
for(int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i];
while(top) push_down(sta[top--]);
while(!isroot(x)&&!isroot(fa[x]))
{
int p=getlc(x),q=getlc(fa[x]);
p==q?(rot(fa[x],q),rot(x,p)):(rot(x,p),rot(x,q));
}
if(!isroot(x)) rot(x,getlc(x));
update(x);
}
void access(int x)
{
for(int t=0;x;t=x,x=fa[x])
{
splay(x);
ch[x][1]=t;
update(x);
}
}
void makeroot(int x) {access(x);splay(x);rev[x]^=1;swap(d1[x],d2[x]);}
struct E{
int v,next;
}edge[maxn*2];
void init()
{
tot=-1;
memset(rev,0,sizeof(rev));
memset(ch,0,sizeof(ch));
}
{
}
void dfs(int u,int father)
{
fa[u]=father;
{
int v=edge[i].v;
if(v==father) continue;
dfs(v,u);
}
}
int main()
{
init();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
int u,v,op;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
}
dfs(1,0);
scanf("%d",&op);
while(op--)
{
scanf("%d%d",&u,&v);
makeroot(u);
access(v);
splay(v);
printf("%d\n",d1[v]);
}
return 0;
}
```

Followed by: