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

## what's wrong with this problem?

Posted by I_love_Wang_Ye at 2009-05-14 08:15:58 on Problem 3728
```#include <stdio.h>
#define MAXN 50010
int n, h[MAXN], d[MAXN*2], p[MAXN*2];
int depth[MAXN], price[MAXN];
int upper[MAXN][16], maxprice[MAXN][16], minprice[MAXN][16];
int getmax(int a, int b)
{
int ans=a, i;
for (i=15; i>=0; --i)
{
if (depth[a]-(1<<i)>=depth[b])
{
if (price[maxprice[a][i]]>price[ans])
ans=maxprice[a][i];
a=upper[a][i];
}
}
if (price[b]>price[ans])
ans=b;
return ans;
}
int getmin(int a, int b)
{
int ans=a, i;
for (i=15; i>=0; --i)
{
if (depth[a]-(1<<i)>=depth[b])
{
if (price[minprice[a][i]]<price[ans])
ans=minprice[a][i];
a=upper[a][i];
}
}
if (price[b]<price[ans])
ans=b;
return ans;
}
int maxprofit(int a, int b, int c)
{
int ans=0, i1, i2;
i1=getmin(a,c);
i2=getmax(i1,c);
if (price[i2]-price[i1]>ans)
ans=price[i2]-price[i1];
i2=getmax(b,c);
i1=getmin(i2,c);
if (price[i2]-price[i1]>ans)
ans=price[i2]-price[i1];
i1=getmin(a,c);
i2=getmax(b,c);
if (price[i2]-price[i1]>ans)
ans=price[i2]-price[i1];
return ans;
}
int searchup(int a, int b)
{
int i;
for (i=15; i>=0; --i)
{
if (depth[a]-(1<<i)>=depth[b])
a=upper[a][i];
}
for (i=15; i>=0; --i)
{
if (depth[b]-(1<<i)>=depth[a])
b=upper[b][i];
}
if (a!=b)
{
for (i=15; i>=0; --i)
{
if (upper[a][i]!=upper[b][i])
{
a=upper[a][i];
b=upper[b][i];
}
}
a=upper[a][0];
b=upper[b][0];
}
return a;
}
void addedge(int id, int a, int b)
{
d[id]=b;
p[id]=h[a];
h[a]=id;
}
void dfs(int id, int level)
{
int i, j;
depth[id]=level;
for (i=h[id]; i!=0; i=p[i])
{
j=d[i];
if (depth[j]==0)
{
upper[j][0]=id;
dfs(j,level+1);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("poj3728.in","r",stdin);
#endif
int i, j, a, b, q;
scanf("%d",&n);
for (i=1; i<=n; ++i) scanf("%d", &price[i]);
for (i=1; i<=n-1; ++i)
{
scanf("%d%d", &a, &b);
}
dfs(1,1);
for (i=1; i<=n; ++i)
{
minprice[i][0]=i;
maxprice[i][0]=i;
}
for (j=1; j<=15; ++j)
{
for (i=1; i<=n; ++i)
{
a=upper[i][j-1];
b=upper[a][j-1];
upper[i][j]=b;
minprice[i][j]=(price[minprice[i][j-1]]<=price[minprice[a][j-1]]?minprice[i][j-1]:minprice[a][j-1]);
maxprice[i][j]=(price[maxprice[i][j-1]]>=price[maxprice[a][j-1]]?maxprice[i][j-1]:maxprice[a][j-1]);
}
}
for (scanf("%d",&q); q; --q)
{
scanf("%d%d",&a,&b);
printf("%d\n", maxprofit(a,b,searchup(a,b)));
}
return 0;
}
```

Followed by: