代码

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define int long long
using namespace std;
const long long INF=100000000000000LL;
int n,m,cnt,top[100010],tail[100010],siz[100010],fa[100010],son[100010],id[100010],a[100010],dep[100010],pos[100010];
long long f[100010][2],g[100010][2];
vector<int> v[100010];
struct Matrix{
    long long data[2][2];
}dp[400010],val[100010];
Matrix operator * (Matrix x,Matrix y){
    Matrix z;
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            z.data[i][j]=-INF;
            for(int k=0;k<=1;k++) z.data[i][j]=max(z.data[i][j],x.data[i][k]+y.data[k][j]);
        }
    }
    return z;
}
void dfs1(int x,int d,int f){
    dep[x]=d;
    siz[x]=1;
    fa[x]=f;
    int maxn=-1;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==f) continue;
        dfs1(v[x][i],d+1,x);
        if(maxn<siz[v[x][i]]) maxn=siz[v[x][i]],son[x]=v[x][i];
        siz[x]+=siz[v[x][i]];
    }
}
void dfs2(int x,int last){
    id[x]=++cnt;
    pos[id[x]]=x;
    top[x]=last;
    if(!son[x]) return;
    dfs2(son[x],last);
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==fa[x]||v[x][i]==son[x]) continue;
        dfs2(v[x][i],v[x][i]);
    }
}
int dfs3(int x){
    f[x][1]=a[x];
    g[x][1]=a[x];
    if(!son[x]) return tail[x]=x;
    tail[x]=dfs3(son[x]);
    g[x][0]=max(g[x][0],g[x][0]+max(g[son[x]][0],g[son[x]][1]));
    g[x][1]=max(g[x][1],g[x][1]+g[son[x]][0]);
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==fa[x]||v[x][i]==son[x]) continue;
        dfs3(v[x][i]);
        f[x][0]=max(f[x][0],f[x][0]+max(g[v[x][i]][0],g[v[x][i]][1]));
        f[x][1]=max(f[x][1],f[x][1]+g[v[x][i]][0]);
        g[x][0]=max(g[x][0],g[x][0]+max(g[v[x][i]][0],g[v[x][i]][1]));
        g[x][1]=max(g[x][1],g[x][1]+g[v[x][i]][0]);
    }
    return tail[x];
}
void build(int k,int l,int r){
    if(l==r){
        dp[k].data[0][0]=dp[k].data[0][1]=f[pos[l]][0];
        dp[k].data[1][0]=f[pos[l]][1];
        dp[k].data[1][1]=-INF;
        val[l]=dp[k];
        return;
    }
    int mid=(l+r)/2;
    build(2*k,l,mid);
    build(2*k+1,mid+1,r);
    dp[k]=dp[2*k]*dp[2*k+1];
}
void modify(int k,int l,int r,int x){
    if(l==r){
        dp[k]=val[l];
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid) modify(2*k,l,mid,x);
    else modify(2*k+1,mid+1,r,x);
    dp[k]=dp[2*k]*dp[2*k+1]; 
}
Matrix query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y) return dp[k];
    int mid=(l+r)/2;
    if(x<=mid&&mid<y) return query(2*k,l,mid,x,y)*query(2*k+1,mid+1,r,x,y);
    if(x<=mid) return query(2*k,l,mid,x,y);
    return query(2*k+1,mid+1,r,x,y);
}
Matrix ask(int x){
    return query(1,1,n,id[top[x]],id[tail[x]]);
}
void change(int x,int ch){
    val[id[x]].data[1][0]+=ch;
    Matrix bef,nxt;
    while(x){
        bef=ask(x);
        modify(1,1,n,id[x]);
        nxt=ask(x);
        x=fa[top[x]];
        val[id[x]].data[0][0]+=max(nxt.data[0][0],nxt.data[1][0])-max(bef.data[0][0],bef.data[1][0]);
        val[id[x]].data[0][1]=val[id[x]].data[0][0];
        val[id[x]].data[1][0]+=nxt.data[0][0]-bef.data[0][0];
    }
}
signed main(){
    char s[20];
    long long sum=0;
    scanf("%lld %lld %s",&n,&m,s);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum+=a[i];
    long long x,y,z,r,p,q,suma;
    for(int i=1;i<n;i++) scanf("%lld %lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
    dfs1(1,1,0);
    dfs2(1,1);
    dfs3(1);
//	printf("%lld %lld\n",g[1][0],g[1][1]);
    build(1,1,n);
    Matrix ans;
//	printf("%lld\n",max(ans.data[0][0],ans.data[1][0]));
    while(m--){
        scanf("%lld %lld %lld %lld",&x,&y,&z,&r);
        suma=sum;
        change(x,(y?-INF:INF));
        suma+=(y^1)*INF;
        change(z,(r?-INF:INF));
        suma+=(r^1)*INF;
        ans=ask(1);
        change(x,(y?INF:-INF));
        change(z,(r?INF:-INF));
        if(suma-max(ans.data[0][0],ans.data[1][0])<INF) printf("%lld\n",suma-max(ans.data[0][0],ans.data[1][0]));
        else printf("-1\n");
    }
    return 0;
}

评测结果