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

## AC程序。不容易呀！！！

Posted by zhangxinkun at 2013-12-01 14:44:48 on Problem 3728
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define MAX 50001
using namespace std;
int n,m;
int ne;
struct edge
{
int from,to,next;
int weight;
}P[MAX*2];
int w[MAX],deep[MAX];
int visit[MAX];
int parent[MAX];
int f[MAX][20],fmax[MAX][20],fmin[MAX][20],fdmax[MAX][20],fdmin[MAX][20];
void insert(int x,int y,int weight)
{
}
void dfs(int now,int fa,int step)
{
int i,j;
int next;
visit[now]=true;
deep[now]=step;
parent[now]=fa;
for(i=0;(1<<i)<=deep[now]+1;i++)
if(f[now][i - 1] != - 1)
{
f[now][i] = f[f[now][i - 1]][i - 1];
if(f[now][i]==-1) continue;
fmax[now][i] = max(fmax[now][i - 1], fmax[f[now][i - 1]][i - 1]);
fmin[now][i] = min(fmin[now][i - 1], fmin[f[now][i - 1]][i - 1]);
fdmax[now][i] = max(fdmax[f[now][i - 1]][i - 1],max(fdmax[now][i - 1],fmax[f[now][i - 1]][i - 1] - fmin[now][i - 1]));
fdmin[now][i] = min(fdmin[f[now][i - 1]][i - 1],min(fdmin[now][i - 1],fmin[f[now][i - 1]][i - 1] - fmax[now][i - 1]));
}
{
next=P[i].to;
if(visit[next]) continue;
f[next][0]=now;
fmax[next][0]=max(w[now],w[next]);
fmin[next][0]=min(w[now],w[next]);
fdmax[next][0]=w[now]-w[next];
fdmin[next][0]=w[now]-w[next];
dfs(next,now,step+1);
}
}
int LCA(int a,int b)
{
int i,j;
if(deep[a]<deep[b]) swap(a,b);
i=0;
while(deep[a]>=(1<<i))
i++;
i--;
for(j=i;j>=0;j--)
if(deep[a]-(1<<j)>=deep[b])
a=f[a][j];
if(a==b)
return a;
for(j=i;j>=0;j--)
if(f[a][j]!=-1&&f[a][j]!=f[b][j])
{
a=f[a][j];
b=f[b][j];
}
return parent[a];
}
int bb[2][35];
bool flg[35];
void get_max_min(int a,int b,int &ma,int &mi,int &mca,int &mci)
{
int i,j;
memset(flg,0,sizeof flg);
ma = mi = w[a];
mca = mci = w[b] - w[a];
for(i = deep[a] - deep[b],j = 0; i; i >>= 1, ++ j) if(i & 1)
{
ma = max(ma,fmax[a][j]);
mi = min(mi,fmin[a][j]);
mca = max(mca,fdmax[a][j]);
mci = min(mci,fdmin[a][j]);
bb[0][j] = fmax[a][j];
bb[1][j] = fmin[a][j];
flg[j] = 1;
a = f[a][j];
}
for(i = 16 - 1; i > 0; -- i)
for(j = i - 1; j >= 0; -- j)
if(flg[i] && flg[j])
{
mca = max(mca,bb[0][i] - bb[1][j]);
mci = min(mci,bb[1][i] - bb[0][j]);
}
}
int main()
{
int i,j;
int x,y,weight;
ne=2;
memset(f,-1,sizeof(f));
memset(fmax,0xfc,sizeof fmax);
memset(fmin,0x7f,sizeof fmin);
memset(fdmax,0xfc,sizeof fdmax);
memset(fdmin,0x7f,sizeof fdmin);
memset(visit,0,sizeof(visit));
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
insert(x,y,1);
}
dfs(1,-1,0);
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&x,&y);
int c=LCA(x,y);
int ma[2],mi[2],mca[2],mci[2],ans = 0;
get_max_min(x,c,ma[0],mi[0],mca[0],mci[0]);
get_max_min(y,c,ma[1],mi[1],mca[1],mci[1]);
ans = max(0,max(mca[0], - mci[1]));
ans = max(ans,ma[1] - mi[0]);
printf("%d\n",ans);
}
return 0;
}
```

Followed by: