题目链接：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);
}