代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>

#define rg register
#define il inline
#define MX (100000+5)
#define INF (1ll<<45)
#define int long long

il int max(int a ,int b){
    return a > b ? a : b;
}

int head[MX] ,tot;
struct edge{
    int node ,next;
}h[MX<<1];
il void addedge(int u ,int v){
    h[++tot].next = head[u];
    head[u] = tot;
    h[tot].node = v;
}

int n ,m;
int v[MX];
int fa[MX] ,dep[MX] ,size[MX] ,hson[MX];
int top[MX] ,id[MX] ,cnt ,end[MX] ,refer[MX];

struct matrix{
    int a[3][3];
    matrix(){
        memset(a,0,sizeof(0));
    }
    matrix operator *(const matrix b){
        matrix c;
        for(rg int i = 1 ;i <= 2 ;++i){
            for(rg int j = 1 ;j <= 2 ;++j){
                c.a[i][j] = -INF;
            }
        }
        for(rg int i = 1 ;i <= 2 ;++i ){
            for(rg int j = 1 ;j <= 2 ;++j ){
                for(rg int k = 1 ;k <= 2 ;++k ){
                    c.a[i][j] = max(a[i][k] + b.a[k][j] ,c.a[i][j]);
                }
            }
        }
        return c;
    }
	void out(){
		for(rg int i = 1 ; i <= 2 ; ++i){
			for(rg int j = 1 ; j <= 2 ; ++j){
				printf("%-3lld " ,a[i][j]);
			}
			putchar('\n');
		}
	}
}LDP[MX];

struct node{
    int l ,r;
    matrix MAT;
    node *lch ,*rch;
}*root;

inline void pushup(node *x){
    x->MAT = x->lch->MAT * x->rch->MAT;
}

il node *build(int l ,int r){
    node *x = new node;
    x->l = l ,x->r = r;
    if(l == r){
        x->MAT = LDP[refer[l]];
		//printf("Initailizing Matrix #%d = LDP[%d] \n",l,refer[l]);
		//x->MAT.out();
        x->lch = x->rch = NULL;
    }
    else{
        int mid = x->l + x->r >> 1;
        x->lch = build(l ,mid);
        x->rch = build(mid + 1 ,r);
        pushup(x);
    }
    return x;
}

matrix muti(node *x ,int l ,int r){
    if(l <= x->l && x->r <= r){
		//puts("//////////////////////////////////////");
		//printf("muti [%d %d] is : \n" ,x->l ,x->r);
		//x->MAT.out();
		//puts("//////////////////////////////////////");
        return x->MAT;
    }
    else{
        int mid = x->l + x->r >> 1;
        if(mid < l) return muti(x->rch ,l ,r);
        if(mid >= r)    return muti(x->lch ,l ,r);
        return muti(x->lch ,l ,r) * muti(x->rch ,l ,r);
    }
}

il void Change(node *x ,int pos){
    if(x->l == pos && x->r == pos)  x->MAT = LDP[refer[pos]];
    else{
        int mid = x->l + x->r >> 1;
        if(mid >= pos)    Change(x->lch ,pos);
        if(mid < pos)     Change(x->rch ,pos);
        pushup(x);
    }
}

il void change(int pos ,int val){
    LDP[pos].a[2][1] += val - v[pos];
    v[pos] = val;
    matrix od ,nw;
    while(pos){
		//printf("Querying multiply on [%d %d] \n" ,id[top[pos]] ,id[end[top[pos]]]);
        od = muti(root ,id[top[pos]] ,id[end[top[pos]]]);
        Change(root ,id[pos]);
		//printf("Changing matrix #%d \n" ,pos);
		//LDP[pos].out();
        nw = muti(root ,id[top[pos]] ,id[end[top[pos]]]);
        pos = fa[top[pos]];
        LDP[pos].a[1][1] += max(nw.a[1][1] ,nw.a[2][1]) - max(od.a[1][1] ,od.a[2][1]);
        LDP[pos].a[1][2] = LDP[pos].a[1][1];
        LDP[pos].a[2][1] += nw.a[1][1] - od.a[1][1];
    }
}

il void dfs1(int x ,int f ,int _dp){
    fa[x] = f;
    dep[x] = _dp;
    size[x] = 1;
    int hsss = 0;
    for(rg int i = head[x] ,d ; i ; i = h[i].next){
        d = h[i].node;
        if(d == f)  continue;
        dfs1(d ,x ,_dp + 1);
        size[x] += size[d];
        if(size[d] > hsss){
            hsss = size[d];
            hson[x] = d;
        }
    }
}
il void dfs2(int x,int tp){
    top[x] = tp;
    id[x] = ++cnt;
    refer[cnt] = x;
    if(hson[x]){
        dfs2(hson[x] ,tp);
        end[x] = end[hson[x]];
    }
    else{
        end[x] = x;
        return;
    }
    for(rg int i = head[x] ,d ; i ; i = h[i].next){
        d = h[i].node;
        if(d == fa[x] || d == hson[x])  continue;
        dfs2(d ,d);
    }
}
namespace brute{
    int dp[MX][2] ,ldp[MX][2];
    void dapai(int x){
        ldp[x][1] = v[x];
        for(rg int i = head[x] ,d ; i ; i = h[i].next){
            d = h[i].node;
            if(d == hson[x] || d == fa[x])  continue;
            dapai(d);
            ldp[x][0] += max(dp[d][1] ,dp[d][0]);
            ldp[x][1] += dp[d][0];
        }
        dp[x][0] = ldp[x][0] ,dp[x][1] = ldp[x][1];
        if(hson[x]) dapai(hson[x]);
        else goto x;
        dp[x][0] += max(dp[hson[x]][1] ,dp[hson[x]][0]);
        dp[x][1] += dp[hson[x]][0];
        
		x: ;
        LDP[x].a[1][1] = LDP[x].a[1][2] = ldp[x][0];
        LDP[x].a[2][1] = ldp[x][1];
		LDP[x].a[2][2] = -INF;
    }
	void out(){
		for(rg int i = 1 ; i <= n ; ++i)	printf("%lld ",dp[i]);
	}
}
int allv = 0;

signed main(){
	char type[85];
    scanf("%lld%lld%s",&n,&m,type);
    for(rg int i = 1 ; i <= n ; ++i){
        scanf("%lld" ,v + i);
		allv += v[i];
    }
    for(rg int i = 1 ,u ,v ; i < n ; ++i){
        scanf("%lld%lld" ,&u ,&v);
        addedge(u ,v);
        addedge(v ,u);
    }
	
    dfs1(1 ,0 ,1);
    dfs2(1 ,1);
	brute::dapai(1);
    root = build(1 ,n);
	
	for(rg int i = 1 ; i <= n ; ++i){
		//printf("hson[%i] = %d \n" ,i ,hson[i]);
	}

	for(rg int i = 1 ; i <= n ; ++i){
		//printf("#%d: \n",i);
		//LDP[i].out();
	}
    for(rg int i = 1 ,x ,t1 ,y ,t2 ,Ans ; i <= m ; ++i){
		Ans = 0;
        scanf("%lld%lld%lld%lld" ,&x ,&t1 ,&y ,&t2);
		int aftvx = v[x] , aftvy = v[y];
		if(t1){	//强制选就改成 -INF 这样子他不会在最大权独立集出现 所以一定会在最小权覆盖集上
			change(x ,-INF);
			//Ans += v[x];
		}
		else{	//强制不选就改成 INF 一定会在最大权独立集出现 所以一定不会在在最小权覆盖集上
			Ans += v[x];
			change(x ,INF);
		}
        if(t2){
			change(y ,-INF);
			//Ans += v[y];
		}
		else{
			Ans += v[y];
			change(y ,INF);
		}
		//printf("ASKING [%d %d] \n" ,id[i] ,id[end[1]]);
        matrix ans = muti(root ,id[1] ,id[end[1]]);
		if(!t1){
			Ans -= INF;
		}
		if(!t2){
			Ans -= INF;
		}
		change(x ,aftvx);
		change(y ,aftvy);
		//printf("");
		Ans += max(ans.a[1][1] ,ans.a[2][1]);
		//printf("最大权独立集为 %lld ANS = %lld\n",max(ans.a[1][1] ,ans.a[2][1]) , Ans);
		//ans.out();
        printf("%lld \n" ,Ans >= 0 ? allv - Ans : -1);
    }
    return 0;
}

评测结果