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

Tarjan离线，做了好久才做出来，纪念一下

Posted by OZY123 at 2016-01-04 13:19:11 on Problem 3728
```#include<cstdio>
#include<cstring>
const int N=50005;
int n,m;
struct qq
{
int x;
int y;
int last;
};
qq s[N*2];
qq s1[N*2];
qq s2[N*2];
int k[N];
int last[N];
int last1[N];
int last2[N];
int ans[N];
int num=0,num1=0;
int f[N];
bool p[N];
int up[N];
int down[N];
int max[N];
int min[N];
int Max (int x,int y){return x>y?x:y;}
int Min (int x,int y){return x<y?x:y;}
void init (int x,int y)
{
num++;
s[num].x=x;
s[num].y=y;
s[num].last=last[x];
last[x]=num;
}
void init2 (int u,int k)
{
num1++;
s2[num1].x=k;
s2[num1].last=last2[u];
last2[u]=num1;
}
void init1 (int x,int y,int z)
{
s1[z].x=x;
s1[z].y=y;
s1[z].last=last1[x];
last1[x]=z;
}

int find (int x)
{
if (f[x]==x) return f[x];
int fa1=f[x];
f[x]=find(f[x]);
up[x]=Max(up[x],Max(up[fa1],max[fa1]-min[x]));
down[x]=Max(down[x],Max(down[fa1],max[x]-min[fa1]));
max[x]=Max(max[x],max[fa1]);
min[x]=Min(min[x],min[fa1]);
return f[x];
}
void TJ (int x)
{
for (int u=last1[x];u!=-1;u=s1[u].last)
if (p[s1[u].y])
{
int lca=find(s1[u].y);
init2(lca,u);
}

f[x]=x;
p[x]=true;
for (int u=last[x];u!=-1;u=s[u].last)
{
if (p[s[u].y]==false)
{
TJ(s[u].y);
f[s[u].y]=x;
}
}
for(int u=last2[x];u!=-1;u=s2[u].last)
{
int k=s2[u].x,x=s1[k].x,y=s1[k].y;
if (k>m)
{
k-=m;
int t1=x;x=y;y=t1;
}
find(x); find(y);
ans[k] = Max(up[x] , down[y]);
ans[k] = Max(ans[k] , max[y] - min[x]);
}
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
num=0;num1=0;
memset(last2,-1,sizeof(last2));
memset(p,false,sizeof(p));
memset(last,-1,sizeof(last));
memset(last1,-1,sizeof(last1));
for (int u=1;u<=n;u++)
{
int a;
scanf("%d",&a);
max[u]=min[u]=a;
up[u]=down[u]=0;
}
for (int u=1;u<n;u++)
{
int x,y;
scanf("%d%d",&x,&y);
init(x,y);
init(y,x);
}
scanf("%d",&m);
for (int u=1;u<=m;u++)
{
int x,y;
scanf("%d%d",&x,&y);
init1(x,y,u);
init1(y,x,u+m);
}
TJ(1);
for (int u=1;u<=m;u++) printf("%d\n",ans[u]);
}
return 0;
}```

Followed by: