代码

#include <bits/stdc++.h>
using namespace std;

namespace AllRangeApply_Define{
#define CIN const int
#define il inline
#define l2(x) __lg(x)
#define MJY(p) freopen(p".in","r",stdin);freopen(p".out","w",stdout);
#define fileread(p) freopen(p".in","r",stdin);
#define filewrite(p) freopen(p".out","w",stdout);

#define endctime end = clock(); \
cerr<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<"\n";

#define endtime end = clock(); \
fprintf(stderr,"time = %.4lf s\n ",double(end-start)/CLOCKS_PER_SEC);

#define starttime clock_t start,end; \
start = clock();

#define mstart bool Med;
#define mend bool Mbe;
#define cmem fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);

// temp define is following
#define int long long

}

namespace Atomic{
namespace normalSTD{
void speed_up(int opt) {
	if(opt) {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);cout.tie(nullptr);
	}
}
}

namespace fastSTD{
int read() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + 48);
}

}

namespace SuperSTD{
struct FastIO
{
#define get( ) getchar( )
#define put(x) putchar(x)
public:
	inline FastIO &operator >>(char &t)  { t = get(); return *this; }
	inline FastIO &operator >>(char *t)  { while((*t = get()) != '\n') *(++t) = '\0'; return *this; }
	template <typename type>
	inline FastIO &operator >>(type &x)  { x = 0; register int sig = 1; register char ch = get();
		while (ch < 48 || ch > 57) { if (ch == '-') sig = -1; ch = get(); }
		while (ch > 47 && ch < 58) x = (x << 3) + (x << 1) + (ch ^ 48),
		ch = get(); x *= sig; return *this; }
	template <typename type>
	inline FastIO &operator <<(type  x)  { if (!x) put('0'); if (x < 0) put('-'), x = -x; static char vec[50];
		register int len = 0; while (x) vec[len++] = x % 10 + '0', x /= 10;
		while (len--) put(vec[len]); return *this; }
	template <typename type>
	inline FastIO &operator <<(type *t)  { for (; *t; t++) put(*t); return *this; }
	inline FastIO &operator <<(char  t)  { put(t); return *this; }
}IO;
}
}

namespace my{
using namespace AllRangeApply_Define;
using namespace Atomic::normalSTD;
//using namespace Atomic::fastSTD;
//using namespace Atomic::SuperSTD;

CIN N = 1e5+5,INF = 5e9;

struct Edge{
	int nxt,to;
}edge[N<<1];
int head[N],cnt;

void init(){
	memset(head,-1,sizeof(head));
	for(int i = 0;i<(N<<1);i++) edge[i].nxt = -1;
	cnt = 0;
}

void addedge(int u,int v){
	edge[cnt].nxt = head[u];
	edge[cnt].to = v;
	head[u] = cnt++;
}

int F[N][2],w[N];

struct matrix{
	int m[2][2];
	matrix(){m[0][0] = m[1][0] = m[0][1] = m[1][1] = INF;}
	int* operator [](const int pos) {return m[pos];}
	friend matrix operator *(matrix a,matrix b){
		matrix c;
		for(int i = 0;i<2;i++) 
			for(int j = 0;j<2;j++) 
				for(int k = 0;k<2;k++) 
					c[i][j] = min(c[i][j],a[i][k] + b[k][j]);
		return c;
	}
};

matrix k[N];
int ed[N],son[N],fa[N],size[N],dep[N],id[N],dfn[N],top[N];
int num;
int n,m;

void dfs1(int x,int f){
	fa[x] = f;
	size[x] = 1;
	dep[x] = dep[f] + 1;
	for(int i = head[x];~i;i = edge[i].nxt){
		int y = edge[i].to;
		if(y ^ f) {
			dfs1(y,x);
			size[x] += size[y];
			if(size[son[x]] < size[y]) son[x] = y;
		}
	}
}

void dfs2(int x,int topx){
	id[x] = ++num;
	dfn[num] = x;
	top[x] = topx;

	ed[topx] = max(ed[topx],num);

	F[x][0] = 0;
	F[x][1] = w[x];
	k[x][0][1] = 0;
	k[x][1][0] = k[x][1][1] = w[x];
	if(!son[x]) return;
	dfs2(son[x],topx);
	F[x][0] += F[son[x]][1];
	F[x][1] += min(F[son[x]][1],F[son[x]][0]);
	for(int i = head[x];~i;i = edge[i].nxt){
		int y = edge[i].to;
		if(y ^ fa[x] && y ^ son[x]) {
			dfs2(y,y);
			F[x][0] += F[y][1];
			F[x][1] += min(F[y][0],F[y][1]);
			k[x][0][1] += F[y][1];
			k[x][1][0] += min(F[y][0],F[y][1]);
			k[x][1][1] = k[x][1][0];
		}
	}
}

namespace sgm{
#define ls (p << 1)
#define rs (ls | 1)
#define mid ((pl + pr) >> 1)

matrix t[N<<2];

void push_up(int p){
	t[p] = t[ls] * t[rs];
}

void build(int p,int pl,int pr){
	if(pl == pr) {
		t[p] = k[dfn[pl]];
		return;
	}
	build(ls,pl,mid);
	build(rs,mid+1,pr);
	push_up(p);
}

void update(int p,int pl,int pr,int kk){
	if(pl == pr && pl == kk) {
		t[p] = k[dfn[pl]];
		return;
	}
	if(kk <= mid) update(ls,pl,mid,kk);
	else update(rs,mid+1,pr,kk);
	push_up(p);
}

matrix query(int p,int pl,int pr,int l,int r){
	if(l <= pl && pr <= r) return t[p];
	if(r <= mid) return query(ls,pl,mid,l,r);
	else if(l > mid) return query(rs,mid+1,pr,l,r);
	else return query(ls,pl,mid,l,r) * query(rs,mid+1,pr,l,r);
}

}

void update(int x,int opt,int d){
	if(!opt){
		k[x][1][0] += d * INF;
		k[x][1][1] = k[x][1][0];
	}else {
		k[x][0][1] += d * INF;	
	}
	

	matrix fir,sec;
	while(x != 0) {
		fir = sgm::query(1,1,n,id[top[x]],ed[top[x]]);
		sgm::update(1,1,n,id[x]);
		sec = sgm::query(1,1,n,id[top[x]],ed[top[x]]);
		x = fa[top[x]];

		k[x][1][0] += min(sec[0][1],sec[1][1]) - min(fir[0][1],fir[1][1]);
		k[x][1][1] = k[x][1][0];
		k[x][0][1] += sec[1][1] - fir[1][1];
	}
}



string opt;

signed main(){
	speed_up(true);
	
	// fileread("P5024_22")
	
	init();

	cin>>n>>m;
	cin>>opt;
	for(int i = 1;i<=n;i++) cin>>w[i];
	for(int i = 1;i<n;i++) {
		int u,v;
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	
	dfs1(1,0);
	dfs2(1,1);
	sgm::build(1,1,n);

	while(m--){
		int a,x,b,y;
		cin>>a>>x>>b>>y;
        if(!x && !y && (fa[b] == a || fa[a] == b)){
            cout<<-1<<'\n';
            continue;
        }
		update(a,x,1);
		update(b,y,1);
		matrix ans = sgm::query(1,1,n,id[1],ed[1]);
		int res = min(ans[1][1],ans[0][1]);
		cout<<res<<'\n';
		update(a,x,-1);
		update(b,y,-1);
	}


	return 0;
}

}
signed main() {
	return my::main();
}

评测结果