题意很简单
给一个树(n < 5w) 每个点有个权值，代表商品价格
若干个询问(5w)
对每个询问，问的是从u点走到v点(简单路径），商人在这个路径中的某点买入商品，然后在某点再卖出商品， 最大可能是多少
注意一条路径上只能买卖一次，先买才能卖
- *分析:先求出点u,v的最近公共祖先f,然后求u->f->v的利润最大值maxval
- 对于这个maxval可能有三种情况:
- 1:maxval是u->f的maxval
- 2:maxval是f->v的maxval
- 3:maxval是u->f的最小w[i]减去f->v的最大w[i]
- 分析到这很明显需要设置4个变量来求maxval:
- up[u]表示u->f的最大maxval
- down[u]表示f->u的最大maxval
- maxw[u]表示u-f的最大w[i]
- minw[u]表示u-f的最小w[i]
- 所以maxval=max(max(up[u],down[v]),maxw[v]-minw[u]);
- 现在问题就是如何快速的求出这四个变量,在这里我们可以对u,v的LCA(u,v)进行分类解决
- 对于LCA(u,v)是f的询问全部求出,然后再求LCA(u,v)是f的父亲的询问
- 这样当我们求LCA(u,v)是f的父亲的询问的时候就可以借用已经求出的LCA(u,v)是f的询问
- 的结果,这样就不用反复去求u->f的那四个变量值,u->father[f]也能快速求出
- 这个变化主要在寻找father[v]这个过程中进行,具体看代码
/*分析:先求出点u,v的最近公共祖先f,然后求u->f->v的利润最大值maxval
对于这个maxval可能有三种情况:
1:maxval是u->f的maxval
2:maxval是f->v的maxval
3:maxval是u->f的最小w[i]减去f->v的最大w[i]
分析到这很明显需要设置4个变量来求maxval:
up[u]表示u->f的最大maxval
down[u]表示f->u的最大maxval
maxw[u]表示u-f的最大w[i]
minw[u]表示u-f的最小w[i]
所以maxval=max(max(up[u],down[v]),maxw[v]-minw[u]);
现在问题就是如何快速的求出这四个变量,在这里我们可以对u,v的LCA(u,v)进行分类解决
对于LCA(u,v)是f的询问全部求出,然后再求LCA(u,v)是f的父亲的询问
这样当我们求LCA(u,v)是f的父亲的询问的时候就可以借用已经求出的LCA(u,v)是f的询问
的结果,这样就不用反复去求u->f的那四个变量值,u->father[f]也能快速求出
这个变化主要在寻找father[v]这个过程中进行,具体看代码
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std; const int MAX=+;
int n,m,size;
int uu[MAX],vv[MAX],ww[MAX],sum[MAX];
int up[MAX],down[MAX],maxw[MAX],minw[MAX],father[MAX];
int head[MAX],head2[MAX],head3[MAX];
bool mark[MAX]; struct Edge{
int v,id,next;
Edge(){}
Edge(int V,int ID,int NEXT):v(V),id(ID),next(NEXT){}
}edge[MAX*],edge2[MAX*],edge3[MAX*]; void Init(int num){
for(int i=;i<=num;++i)head[i]=head2[i]=head3[i]=-,mark[i]=false;
size=;
}
void InsertEdge(int u,int v,int id){
edge[size]=Edge(v,id,head[u]);
head[u]=size++;
}
void InsertEdge2(int u,int v,int id){
edge2[size]=Edge(v,id,head2[u]);
head2[u]=size++;
}
void InsertEdge3(int u,int v,int id){
edge3[size]=Edge(v,id,head3[u]);
head3[u]=size++;
}
int findset(int v){
if(v == father[v])return father[v];
int fa=father[v];
father[v]=findset(father[v]);
up[v]=max(max(up[v],up[fa]),maxw[fa]-minw[v]);
down[v]=max(max(down[v],down[fa]),maxw[v]-minw[fa]);
maxw[v]=max(maxw[v],maxw[fa]);
minw[v]=min(minw[v],minw[fa]);
return father[v];
}
void LCA(int u){
mark[u]=true;
father[u]=u;
for(int i=head2[u];i != -;i=edge2[i].next){//对LCA(u,v)进行分类
int v=edge2[i].v,id=edge2[i].id;
if(!mark[v])continue;
int f=findset(v);
InsertEdge3(f,v,id);
}
for(int i=head[u];i != -;i=edge[i].next){
int v=edge[i].v;
if(mark[v])continue;
LCA(v);
father[v]=u;
}
for(int i=head3[u];i != -;i=edge3[i].next){
int id=edge3[i].id;
findset(uu[id]);
findset(vv[id]);
sum[id]=max(max(up[uu[id]],down[vv[id]]),maxw[vv[id]]-minw[uu[id]]);
}
}
int main(){
int u,v;
while(~scanf("%d",&n)){
Init(n);
for(int i=;i<=n;++i){
scanf("%d",ww+i);
up[i]=down[i]=;
maxw[i]=minw[i]=ww[i];
}
for(int i=;i<n;++i){
scanf("%d%d",&u,&v);
InsertEdge(u,v,i);
InsertEdge(v,u,i);
}
size=;
scanf("%d",&m);
for(int i=;i<m;++i){
scanf("%d%d",&uu[i],&vv[i]);
InsertEdge2(uu[i],vv[i],i);
InsertEdge2(vv[i],uu[i],i);
}
size=;
LCA();
for(int i=;i<m;++i)printf("%d\n",sum[i]);
}
return ;
}
RMQ做法
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std; const int MAX=+;
int n,m,size,top;
int uu[MAX],vv[MAX],ww[MAX],anc[MAX];
int up[MAX][],down[MAX][],maxw[MAX][],minw[MAX][],deep[MAX];
int head[MAX],head2[MAX],bin[MAX],stack[MAX],mp[MAX][],father[MAX];
bool mark[MAX]; struct Edge{
int v,id,next;
Edge(){}
Edge(int V,int ID,int NEXT):v(V),id(ID),next(NEXT){}
}edge[MAX*],edge2[MAX*]; void Init(int num){
for(int i=;i<=num;++i)head[i]=head2[i]=-,mark[i]=false;
size=top=;
}
void InsertEdge(int u,int v,int id){
edge[size]=Edge(v,id,head[u]);
head[u]=size++;
}
void InsertEdge2(int u,int v,int id){
edge2[size]=Edge(v,id,head2[u]);
head2[u]=size++;
}
void dfs(int u,int father,int k){
deep[u]=k;
for(int i=head[u];i != -;i=edge[i].next){
int v=edge[i].v;
if(v == father)continue;
dfs(v,u,k+);
}
}
void RMQ(int u,int father){
stack[++top]=u;
int fa=stack[top-];
up[u][]=down[u][]=;
maxw[u][]=minw[u][]=ww[u];
for(int i=;bin[i]<=top;++i){//2^i<=top
fa=stack[top-bin[i-]];
up[u][i]=max(max(up[u][i-],up[fa][i-]),maxw[fa][i-]-minw[u][i-]);
down[u][i]=max(max(down[u][i-],down[fa][i-]),maxw[u][i-]-minw[fa][i-]);
maxw[u][i]=max(maxw[u][i-],maxw[fa][i-]);
minw[u][i]=min(minw[u][i-],minw[fa][i-]);
mp[u][i]=stack[top-bin[i]];
}
for(int i=head[u];i != -;i=edge[i].next){
int v=edge[i].v;
if(v == father)continue;
RMQ(v,u);
}
--top;
}
int findset(int v){
if(v != father[v])father[v]=findset(father[v]);
return father[v];
}
void LCA(int u){
mark[u]=true;
father[u]=u;
for(int i=head2[u];i != -;i=edge2[i].next){
int v=edge2[i].v,id=edge2[i].id;
if(!mark[v])continue;
anc[id]=findset(v);
}
for(int i=head[u];i != -;i=edge[i].next){
int v=edge[i].v;
if(mark[v])continue;
LCA(v);
father[v]=u;
}
}
int search(int x){
int i=;
while(bin[i+]<=x)++i;
return i;
}
int Minw(int u,int anc){
int i=search(deep[u]-deep[anc]+);
if(bin[i] == deep[u]-deep[anc]+)return minw[u][i];
return min(minw[u][i],Minw(mp[u][i],anc));
}
int Maxw(int u,int anc){
int i=search(deep[u]-deep[anc]+);
if(bin[i] == deep[u]-deep[anc]+)return maxw[u][i];
return max(maxw[u][i],Maxw(mp[u][i],anc));
}
int Down(int u,int anc){
int i=search(deep[u]-deep[anc]+);
if(bin[i] == deep[u]-deep[anc]+)return down[u][i];
int downfa=Down(mp[u][i],anc);
downfa=max(downfa,down[u][i]);
int minwfa=Minw(mp[u][i],anc);
return max(downfa,maxw[u][i]-minwfa);
}
int UP(int u,int anc){
int i=search(deep[u]-deep[anc]+);
if(bin[i] == deep[u]-deep[anc]+)return up[u][i];
int upfa=UP(mp[u][i],anc);
upfa=max(upfa,up[u][i]);
int maxwfa=Maxw(mp[u][i],anc);
return max(upfa,maxwfa-minw[u][i]);
}
int main(){
bin[]=;
for(int i=;bin[i-]<MAX;++i)bin[i]=bin[i-]*;
int u,v;
while(~scanf("%d",&n)){
Init(n);
for(int i=;i<=n;++i)scanf("%d",ww+i);
for(int i=;i<n;++i){
scanf("%d%d",&u,&v);
InsertEdge(u,v,i);
InsertEdge(v,u,i);
}
size=;
scanf("%d",&m);
for(int i=;i<m;++i){
scanf("%d%d",uu+i,vv+i);
InsertEdge2(uu[i],vv[i],i);
InsertEdge2(vv[i],uu[i],i);
}
dfs(,-,);
RMQ(,-);
LCA();
for(int i=;i<m;++i){
int upmax=UP(uu[i],anc[i]),downmax=Down(vv[i],anc[i]);
int Minww=Minw(uu[i],anc[i]),Maxww=Maxw(vv[i],anc[i]);
printf("%d\n",max(max(upmax,downmax),Maxww-Minww));
}
}
return ;
}
/*
7
300
11
11
21
10
31
222
1 2
2 3
3 4
4 5
2 6
1 7
1
5 6
*/