代码

#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll INF=1e11;
int Head[N],Next[N<<1],vet[N<<1];
int top[N],fa[N],ch[N][2],son[N],sz[N],lsz[N],stk[N],Fa[N],pre[N];
ll dp[N][2],g[N][2],p[N];
int n,m,u,v,edgenum,a,x,b,y,root,cnt;
char s[10];
inline ll Min(const ll& a, const ll& b){ return a<b?a:b; }
struct Matrix{ ll a[2][2]; };
inline Matrix Get(const ll& x, const ll& y){
    Matrix c;
    c.a[0][0]=INF; c.a[0][1]=x;
    c.a[1][0]=c.a[1][1]=y;
    return c;
}
Matrix tree[N],Node[N];
Matrix operator * (const Matrix& a, const Matrix& b){
    Matrix c;
    c.a[0][0]=Min(a.a[0][0]+b.a[0][0],a.a[0][1]+b.a[1][0]);
    c.a[0][1]=Min(a.a[0][0]+b.a[0][1],a.a[0][1]+b.a[1][1]);
    c.a[1][0]=Min(a.a[1][0]+b.a[0][0],a.a[1][1]+b.a[1][0]);
    c.a[1][1]=Min(a.a[1][0]+b.a[0][1],a.a[1][1]+b.a[1][1]);
    return c;
}
inline void addedge(const int& u, const int& v){
    vet[++edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
inline void pushup(const int& u){ tree[u]=tree[ch[u][0]]*Node[u]*tree[ch[u][1]]; }
inline void update(int u){
    Node[u]=Get(g[u][0],g[u][1]);
    for (; u; u=fa[u]){
        int f=fa[u];
        if (f && ch[f][0]!=u && ch[f][1]!=u){
            g[f][0]-=tree[u].a[1][1]; g[f][1]-=Min(tree[u].a[0][1],tree[u].a[1][1]);
            pushup(u);
            g[f][0]+=tree[u].a[1][1]; g[f][1]+=Min(tree[u].a[0][1],tree[u].a[1][1]);
            Node[f]=Get(g[f][0],g[f][1]);
        } else pushup(u);
    }
}
int build(int l, int r){
    if (l>r) return 0;
    int hav=(pre[r]+pre[l-1]+1)/2;
    int k=lower_bound(pre+l,pre+r+1,hav)-pre,u=stk[k];
    fa[ch[u][0]=build(l,k-1)]=u;
    fa[ch[u][1]=build(k+1,r)]=u;
    pushup(u); return u;
}
void dfs1(int u, int f){
    sz[u]=1; dp[u][1]=p[u]; fa[u]=Fa[u]=f;
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        dp[u][0]+=dp[v][1];
        dp[u][1]+=Min(dp[v][0],dp[v][1]);
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
    lsz[u]=sz[u]-sz[son[u]];
}
void dfs2(int u, int f, int st){
    top[u]=st; g[u][1]=p[u];
    if (son[u]) dfs2(son[u],u,st);
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==son[u] || v==f) continue;
        dfs2(v,u,v);
        g[u][0]+=dp[v][1];
        g[u][1]+=Min(dp[v][0],dp[v][1]);
    }
    Node[u]=Get(g[u][0],g[u][1]);
    if (top[u]==u){
        cnt=0;
        for (int i=u; i; i=son[i]) stk[++cnt]=i,pre[cnt]=pre[cnt-1]+lsz[i];
        int las=fa[u];
        fa[root=build(1,cnt)]=las;
    }
}
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);
    n=read(); m=read(); scanf("%s",s);
    ll *P=p;
    for (register int i=1; i<=n; i++) *(P+i)=read();
    for (register int i=1; i<n; i++){
        u=read(); v=read();
        addedge(u,v); addedge(v,u);
    }
    tree[0].a[0][0]=tree[0].a[1][1]=0;
    tree[0].a[0][1]=tree[0].a[1][0]=INF;
    dfs1(1,0); dfs2(1,0,1);
    for (; m; m--){
        a=read(); x=read(); b=read(); y=read();
        if (!x && !y && (Fa[a]==b || Fa[b]==a)){ puts("-1"); continue; }
        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);
        printf("%lld\n",Min(tree[root].a[0][1],tree[root].a[1][1]));
        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
*/

评测结果