代码

// #pragma GCC optimize(2)
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll INF=(ll)1e11;
int Head[N],vet[N<<1],Next[N<<1];
int n,m,a,x,b,y,u,v,edgenum,Time;
int top[N],sz[N],intime[N],son[N],fa[N],endt[N];
ll g[N][2],dp[N][2],p[N];
char s[10];
#define ls now<<1
#define rs now<<1|1
inline ll Min(const ll& a, const ll& b){ return a<b?a:b; }
struct Matrix{
    ll a[2][2];
    inline Matrix(){ a[0][0]=a[0][1]=a[1][0]=a[1][1]=INF; }
    inline Matrix(ll x, ll y){ a[0][0]=INF; a[0][1]=x; a[1][0]=a[1][1]=y; }
};
Matrix tree[N<<2];
Matrix operator * (const Matrix& a, const Matrix& b){
    Matrix c;
    for (int i=0; i<=1; i++)
        for (int j=0; j<=1; j++)
            for (int k=0; k<=1; k++)
                c.a[i][j]=Min(c.a[i][j],a.a[i][k]+b.a[k][j]);
    return c;
}
inline void addedge(int u, int v){
    edgenum++;
    vet[edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
void update(int now, int l, int r, int x, Matrix val){
    if (l==r){ tree[now]=val; return; }
    int mid=(l+r)>>1;
    if (mid>=x) update(ls,l,mid,x,val);
    else update(rs,mid+1,r,x,val);
    tree[now]=tree[ls]*tree[rs];
}
Matrix query(int now, int l, int r, int x, int y){
    if (l==x && r==y) return tree[now];
    int mid=(l+r)>>1;
    if (mid>=y) return query(ls,l,mid,x,y);
    else if (mid<x) return query(rs,mid+1,r,x,y);
    else return query(ls,l,mid,x,mid)*query(rs,mid+1,r,mid+1,y);
}
void dfs1(int u, int f){
    sz[u]=1; dp[u][1]=p[u];
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
        dp[u][0]+=dp[v][1];
        dp[u][1]+=Min(dp[v][0],dp[v][1]);
    }
}
void dfs2(int u, int f, int st){
    top[u]=st; fa[u]=f; g[u][1]=p[u]; intime[u]=++Time;
    if (!son[u]){
        update(1,1,n,intime[u],Matrix(g[u][0],g[u][1]));
        endt[st]=intime[u]; return;
    }
    dfs2(son[u],u,st);
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (intime[v]) continue;
        g[u][0]+=dp[v][1];
        g[u][1]+=Min(dp[v][0],dp[v][1]);
        dfs2(v,u,v);
    }
    update(1,1,n,intime[u],Matrix(g[u][0],g[u][1]));
}
inline void Update(int u){
    update(1,1,n,intime[u],Matrix(g[u][0],g[u][1]));
    for (u=top[u]; u>1; u=top[fa[u]]){
        Matrix res=query(1,1,n,intime[u],endt[u]);
        g[fa[u]][0]-=dp[u][1];
        g[fa[u]][1]-=Min(dp[u][0],dp[u][1]);
        dp[u][0]=res.a[0][1],dp[u][1]=res.a[1][1];
        g[fa[u]][0]+=dp[u][1];
        g[fa[u]][1]+=Min(dp[u][0],dp[u][1]);
        update(1,1,n,intime[fa[u]],Matrix(g[fa[u]][0],g[fa[u]][1]));
    }
}
inline ll Query(){
    Matrix ans=query(1,1,n,1,endt[1]);
    return Min(ans.a[0][1],ans.a[1][1]);
}
inline int read(){
    int num=0,fu=1; char ch=getchar();
    while (ch<'0' || ch>'9'){ if (ch=='-') fu=0; ch=getchar(); }
    while (ch>='0' && ch<='9'){ num=(num<<3)+(num<<1)+ch-'0'; ch=getchar(); }
    return fu?num:-num;
}
int main(){
    freopen("defense.in","r",stdin);
    freopen("defense.out","w",stdout);
    // scanf("%d%d%s",&n,&m,s);
    n=read(); m=read(); scanf("%s",s);
    for (int i=1; i<=n; i++) p[i]=read();
    for (int i=1; i<n; i++){
        // scanf("%d%d",&u,&v);
        u=read(); v=read();
        addedge(u,v); addedge(v,u);
    }
    dfs1(1,0); dfs2(1,0,1);
    for (; m; m--){
        // scanf("%d%d%d%d",&a,&x,&b,&y);
        a=read(); x=read(); b=read(); y=read();
        x^=1; y^=1;
        ll last1=g[a][x],last2=g[b][y];
        g[a][x]=INF; Update(a);
        g[b][y]=INF; Update(b);
        ll ans=Query();
        if (ans>=INF) puts("-1");
        else printf("%lld\n",ans);
        g[a][x]=last1; Update(a);
        g[b][y]=last2; Update(b);        
    }
    return 0;
}
/*
5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0
*/

评测结果