题目链接:Luogu P5024。
题解
本题有多种写法。
解法 A
思路
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
using std::pair;
using std::make_pair;
using std::swap;
#include<set>
using std::set;
typedef long long ll;
#define INF 0X3F3F3F3F3F3F3F3Fll
const int MAXN=100000+5;
const int MAXLOG2N=20;
const int MAXP=100000+5;
int n,m;
int p[MAXN];
int cnt,head[MAXN],to[MAXN<<1],Next[MAXN<<1];
int dep[MAXN];
int fa[MAXN][MAXLOG2N];
ll f[MAXN][2],g[MAXN][2];
ll h[MAXN][MAXLOG2N][2][2];
set<pair<int,int>/**/> S;
void Init(void);
void Add_Edge(int,int);
void DFS1(int,int,int);
void DFS2(int);
ll Query(int,int,int,int);
int main(void){
register int i;
scanf("%d%d%*s",&n,&m);
for(i=1;i<=n;++i)
scanf("%d",&p[i]);
for(i=1;i<n;++i){
static int u,v;
scanf("%d%d",&u,&v);
Add_Edge(u,v);
Add_Edge(v,u);
S.insert(make_pair(u,v));
S.insert(make_pair(v,u));
}
Init();
while(m--){
static int a,x,b,y;
scanf("%d%d%d%d",&a,&x,&b,&y);
if(!x&&!y&&S.find(make_pair(a,b))!=S.end())
puts("-1");
else
printf("%lld\n",Query(a,x,b,y));
}
return 0;
}
void DFS1(int ID,int father,int depth){
register int i;
fa[ID][0]=father;
dep[ID]=depth;
f[ID][1]=p[ID];
for(i=head[ID];i;i=Next[i])
if(to[i]!=father){
DFS1(to[i],ID,depth+1);
f[ID][0]+=f[to[i]][1];//自己不选儿子选
f[ID][1]+=min(f[to[i]][0],f[to[i]][1]);//自己选了,儿子选、不选都可以
}
for(i=1;i<MAXLOG2N;++i)
fa[ID][i]=fa[fa[ID][i-1]][i-1];
return;
}
void DFS2(int ID){
register int i;
for(i=head[ID];i;i=Next[i])
if(to[i]!=fa[ID][0]){
g[to[i]][0]=g[ID][1]+f[ID][1]-min(f[to[i]][0],f[to[i]][1]);//儿子不选,自己选
g[to[i]][1]=min(g[ID][0]+f[ID][0]-f[to[i]][1],g[to[i]][0]);//儿子选,自己不选
DFS2(to[i]);
}
return;
}
void Init(void){
register int i,j,u,v,w;
DFS1(1,0,1);
DFS2(1);
for(i=1;i<=n;++i){
h[i][0][0][0]=INF;
h[i][0][0][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);
h[i][0][1][0]=f[fa[i][0]][0]-f[i][1];
h[i][0][1][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);
}
for(j=1;j<MAXLOG2N;++j){
for(i=1;i<=n;++i){
fa[i][j]=fa[fa[i][j-1]][j-1];
for(u=0;u<2;++u)
for(v=0;v<2;++v){
h[i][j][u][v]=INF;
for(w=0;w<2;++w)
h[i][j][u][v]=min(h[i][j][u][v],h[i][j-1][u][w]+h[fa[i][j-1]][j-1][w][v]);
}
}
}
return;
}
void Add_Edge(int u,int v){
Next[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
return;
}
ll Query(int a,int x,int b,int y){
register int i,j,k;
ll T[2][2],temp[2][2];
if(dep[a]<dep[b])
swap(a,b),swap(x,y);
memset(T,0X3F,sizeof(T));
T[0][x]=f[a][x];
T[1][y]=f[b][y];
for(i=MAXLOG2N-1;i>=0;--i){
if(dep[fa[a][i]]>=dep[b]){
temp[0][0]=temp[0][1]=INF;
for(j=0;j<2;++j)
for(k=0;k<2;++k)
temp[0][j]=min(temp[0][j],T[0][k]+h[a][i][k][j]);
T[0][0]=temp[0][0],T[0][1]=temp[0][1],a=fa[a][i];
}
}
if(a==b)//b是a的父亲节点
return T[0][y]+g[a][y];//返回除了a以上的和b
for(i=MAXLOG2N-1;i>=0;--i){
if(fa[a][i]!=fa[b][i]){
temp[0][0]=temp[0][1]=temp[1][0]=temp[1][1]=INF;
for(j=0;j<2;j++)
for(k=0;k<2;k++){
temp[0][j]=min(temp[0][j],T[0][k]+h[a][i][k][j]);
temp[1][j]=min(temp[1][j],T[1][k]+h[b][i][k][j]);
}
T[0][0]=temp[0][0],T[0][1]=temp[0][1],a=fa[a][i];
T[1][0]=temp[1][0],T[1][1]=temp[1][1],b=fa[b][i];
}
}
int LCA=fa[a][0];
ll ans1=f[LCA][0]-f[a][1]-f[b][1]+T[0][1]+T[1][1]+g[LCA][0];
ll ans2=f[LCA][1]-min(f[a][0],f[a][1])-min(f[b][0],f[b][1])+min(T[0][0],T[0][1])+min(T[1][0],T[1][1])+g[LCA][1];
return min(ans1,ans2);
}
近期评论