代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>

using namespace std;

typedef long long int_t;

const int_t maxn = 100010;
const int_t inf = 2147483647ll * 192608;
#define lson son[rt][0]
#define rson son[rt][1]

struct matrix{
    int_t mat[3][3];
    matrix(){mat[1][1] = mat[1][2] = mat[2][1] = mat[2][2] = -inf;}
    int_t MAX(){return max(mat[1][1],mat[2][1]);}
    matrix operator *(matrix b){
        matrix c;
        for(int_t i=1;i<=2;i++)
            for(int_t j=1;j<=2;j++)
                for(int_t k=1;k<=2;k++)
                    c.mat[i][j] = max(c.mat[i][j],mat[i][k] + b.mat[k][j]);
        return c;
    }
};

matrix mat[maxn];
int_t f[maxn][2],fa[maxn],val[maxn],son[maxn][2];
vector<int_t> G[maxn];

void pushup(int_t rt){
    mat[rt] = matrix();
    mat[rt].mat[1][1] = mat[rt].mat[1][2] = f[rt][0];
    mat[rt].mat[2][1] = f[rt][1];
    if(lson) mat[rt] = mat[lson] * mat[rt];
    if(rson) mat[rt] = mat[rt] * mat[rson];
}

bool isroot(int_t rt) { return son[fa[rt]][0] != rt && son[fa[rt]][1] != rt; }

void rotate(int_t rt){
    int_t fat = fa[rt], gfa = fa[fat], rs = son[fat][1] == rt, mus = son[rt][!rs];
    if(!isroot(fat)) son[gfa][son[gfa][1] == fat] = rt; son[rt][!rs] = fat; son[fat][rs] = mus;
    if(mus) fa[mus] = fat; fa[rt] = gfa; fa[fat] = rt;
    pushup(fat); pushup(rt);
}

void splay(int_t rt){
    while(!isroot(rt)){
        int_t fat = fa[rt],gfa = fa[fat];
        if(!isroot(fat)) rotate(((son[fat][1] == rt) ^ (son[gfa][1] == fat)) ? rt : fat);
        rotate(rt);
    }
}

void access(int_t rt){
    for(int_t y = 0;rt;y = rt,rt = fa[rt]){
        splay(rt);
        if(rson) 
            f[rt][0] += mat[rson].MAX(),
            f[rt][1] += mat[rson].mat[1][1];
        if(y)
            f[rt][0] -= mat[y].MAX(),
            f[rt][1] -= mat[y].mat[1][1];
        rson = y;
        pushup(rt);
    }
}

void init(int_t rt){
    f[rt][1] = val[rt];
    for(int_t to : G[rt]){
        if(to == fa[rt]) continue;
        fa[to] = rt;
        init(to);
        f[rt][0] += max(f[to][0],f[to][1]);
        f[rt][1] += f[to][0];
    }
    mat[rt].mat[1][1] = mat[rt].mat[1][2] = f[rt][0];
    mat[rt].mat[2][1] = f[rt][1]; 
}

int_t read(){
    int_t x = 0,w = 1;char ch = 0;
    while(!isdigit(ch)) {ch = getchar();if(ch == '-') w = -1;}
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x * w;
}

void modify(int_t x,int_t y){
    access(x); splay(x);
    f[x][1] += y; val[x] += y;
    pushup(x); 
}

int main(){
    int_t n = read(),m = read(),res = 0; string str;cin>>str;
    for(int_t i=1;i<=n;i++) val[i] = read(),res += val[i];
    for(int_t i=1;i<n;i++){
        int_t u = read(),v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init(1);
    while(m--){
        int_t a = read(),x = read(),b = read(),y = read();
        modify( a,x ? -inf : inf );
        modify( b,y ? -inf : inf );
        splay(1);
        if(!x) res += inf; if(!y) res += inf;
        int_t ans = res - mat[1].MAX();
        printf("%lld\n",ans > inf ? -1 : ans);
        if(!x) res -= inf; if(!y) res -= inf;
        modify( a,x ? inf : -inf );
        modify( b,y ? inf : -inf );
    }
}

评测结果