代码

#include<bits/stdc++.h>
#define int64 long long
#define maxn 200010
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define inf (1ll<<62)
#define Inf (int64)1e12
using namespace std;
vector<int> v[maxn];
int n,m,siz[maxn],son[maxn],fa[maxn],vis[maxn],up[maxn],dn[maxn],pos[maxn],t;
int64 f[maxn][2],g[maxn][2],sgm,a[maxn];
struct node{
    int64 a[2][2];
    node(int64 x=0,int64 y=-inf,int64 z=-inf,int64 w=0):a{{x,y},{z,w}}{}
};
node update(node a,node b){
    node r;
    for(int i:{0,1})for(int k:{0,1})for(int j:{0,1})
        r.a[i][j]=max(r.a[i][j],a.a[i][k]+b.a[k][j]);
    return r;
}
struct segTree{
    node a[maxn*4];
    void ins(int x,node v,int p=1,int tl=1,int tr=n){
        if(tl==tr){a[p]=v;return;}
        int mid=tl+tr>>1;
        if(x<=mid)ins(x,v,L(p),tl,mid);
        else ins(x,v,R(p),mid+1,tr);
        a[p]=update(a[L(p)],a[R(p)]);
    }
    node qry(int l,int r,int p=1,int tl=1,int tr=n){
        if(l>r)return node();
        if(l<=tl && tr<=r)return a[p];
        int mid=tl+tr>>1;
        if(r<=mid)return qry(l,r,L(p),tl,mid);
        if(l>mid)return qry(l,r,R(p),mid+1,tr);
        return update(qry(l,r,L(p),tl,mid),qry(l,r,R(p),mid+1,tr));
    }
}tr;
void dfs(int p,int f=0){
    fa[p]=f;siz[p]=1;
    int mx=-1;
    for(int i:v[p])if(i!=f){
        dfs(i,p),siz[p]+=siz[i];
        if(siz[i]>mx)mx=siz[i],son[p]=i;
    }
}
void dfs1(int p,int u){
    pos[p]=++t,up[p]=u,vis[p]=1,dn[u]=p;
    if(son[p])dfs1(son[p],u);
    f[p][1]=g[p][1]=a[p];
    for(int i:v[p])if(!vis[i])
        dfs1(i,i),g[p][0]+=max(f[i][0],f[i][1]),g[p][1]+=f[i][0];
    if(son[p])
        f[p][0]+=g[p][0]+max(f[son[p]][0],f[son[p]][1]),
        f[p][1]+=g[p][1]-a[p]+f[son[p]][0];
    tr.ins(pos[p],{g[p][0],g[p][0],g[p][1],0});
}
void modify(int x,int64 y){
    int o;
    node now=tr.qry(pos[x],pos[o=x]);
    int64 g0=now.a[0][0],g1=now.a[1][0]-a[x]+y;
    for(;x;x=fa[up[x]]){
        node n=tr.qry(pos[up[x]],pos[dn[up[x]]]-1);
        int64 lf0=max(n.a[0][0],n.a[0][1]+a[dn[up[x]]]),lf1=max(n.a[1][0],n.a[1][1]+a[dn[up[x]]]);
        tr.ins(pos[x],{g0,g0,g1,0});
        n=tr.qry(pos[up[x]],pos[dn[up[x]]]-1);
        int64 nv=dn[up[x]]==o?y:a[dn[up[x]]],
            f0=max(n.a[0][0],n.a[0][1]+nv),f1=max(n.a[1][0],n.a[1][1]+nv);
        if(fa[up[x]]){
            n=tr.qry(pos[fa[up[x]]],pos[fa[up[x]]]);
            g0=n.a[0][0]-max(lf0,lf1)+max(f0,f1);
            g1=n.a[1][0]-lf0+f0;
        }
    }
    a[o]=y;
}
int main(){
    scanf("%d%d %*s",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",a+i),sgm+=a[i];
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y),v[y].push_back(x);
    }
    dfs(1);
    dfs1(1,1);
    while(m--){
        int x,xx,y,yy;scanf("%d%d%d%d",&x,&xx,&y,&yy);
        xx^=1,yy^=1;
        int64 oa=a[x],ob=a[y];
        modify(x,xx?Inf:-Inf);modify(y,yy?Inf:-Inf);
        node now=tr.qry(pos[1],pos[dn[1]]-1);
        int64 ans=max({now.a[0][0],now.a[1][0],max(now.a[0][1],now.a[1][1])+a[dn[1]]});
        if(xx)ans+=-Inf+oa;
        if(yy)ans+=-Inf+ob;
        printf("%lld\n",sgm-ans>Inf/2?-1ll:sgm-ans);
        modify(x,oa);modify(y,ob);
    }
    return 0;
}

评测结果