代码

#include <bits/stdc++.h>
#define inf 1e18
#define re register
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
const int N=1e5+100;
int n,m,sz[N],son[N],top[N],End[N],fa[N];
int dfn[N],id[N],cnt,vi[N];
int tot,first[N],nxt[N*2],point[N*2];
long long f[N][2],g[N][2],F[N][2],v[N];
int et[N],ef[N],wt,wf;
struct matrix
{
	long long a[3][3];
	void clear()
	{
		for (re int i=1;i<=2;++i)
		{
			for (re int j=1;j<=2;++j)
			  a[i][j]=inf;
		}
	}
	void init()
	{
		clear();
		for (re int i=1;i<=2;++i) a[i][i]=0;
	}
}tr[N];
matrix Tr[N];
struct node
{
	matrix mul;
}sh[N*4];
matrix operator *(matrix x,matrix y)
{
	matrix ans;
	ans.clear();
	for (re int i=1;i<=2;++i)
	{
		for (re int j=1;j<=2;++j)
		{
			for (re int k=1;k<=2;++k)
			  ans.a[i][j]=min(ans.a[i][j],x.a[i][k]+y.a[k][j]);
		}
	}
	return ans;
}
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch>'9' || ch<'0')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void add_edge(int x,int y)
{
	tot++;
	nxt[tot]=first[x];
	first[x]=tot;
	point[tot]=y;
}
void dfs(int x)
{
	sz[x]=1;
	for (re int i=first[x];i!=-1;i=nxt[i])
	{
		int u=point[i];
		if (u==fa[x]) continue;
		fa[u]=x;
		dfs(u);
		if (sz[u]>sz[son[x]]) son[x]=u;
		sz[x]+=sz[u];
	}
}
void dfs1(int x,int t)
{
	top[x]=t;
	cnt++;
	dfn[x]=cnt;
	id[cnt]=x;
	if (sz[x]==1) End[t]=x;
	if (son[x]) dfs1(son[x],t);
	g[x][1]=v[x];
	for (re int i=first[x];i!=-1;i=nxt[i])
	{
		int u=point[i];
		if (u==fa[x] || u==son[x]) continue;
		dfs1(u,u);
		g[x][0]+=f[u][1],
		g[x][1]+=min(f[u][0],f[u][1]);
	}
	f[x][0]=g[x][0]+f[son[x]][1];
	f[x][1]=g[x][1]+min(f[son[x]][0],f[son[x]][1]);
	tr[x].a[1][1]=inf,tr[x].a[1][2]=g[x][0];
	tr[x].a[2][1]=tr[x].a[2][2]=g[x][1];
	if (sz[x]==1) tr[x].a[1][1]=f[x][0],tr[x].a[2][1]=f[x][1];
}
inline void pushup(int x)
{
	sh[x].mul=sh[x+x].mul*sh[x+x+1].mul;
}
void build(int x,int l,int r)
{
	if (l==r)
	{
		sh[x].mul=tr[id[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(x+x,l,mid);
	build(x+x+1,mid+1,r);
	pushup(x);
}
void change(int x,int l,int r,int wh,matrix V)
{
	if (l==r)
	{
		sh[x].mul=V;
		return;
	}
	int mid=(l+r)>>1;
	if (wh<=mid) change(x+x,l,mid,wh,V);
	else change(x+x+1,mid+1,r,wh,V);
	pushup(x);
}
matrix query(int x,int l,int r,int ll,int rr)
{
	if (ll<=l && rr>=r) return sh[x].mul;
	matrix ans;ans.init();
	int mid=(l+r)>>1;
	if (ll<=mid) ans=query(x+x,l,mid,ll,rr);
	if (rr>mid) ans=ans*query(x+x+1,mid+1,r,ll,rr);
	return ans;
}
void change_path(int x,int op)
{
	if (op==0) tr[x].a[2][1]=tr[x].a[2][2]=inf;
	if (op==1) tr[x].a[1][2]=tr[x].a[1][1]=inf;
	if (!vi[x]) et[++wt]=x,vi[x]=1;
	change(1,1,n,dfn[x],tr[x]);
	int t=top[x];
	while (t)
	{
		matrix p;
		p=query(1,1,n,dfn[top[t]],dfn[End[t]]);
		long long f0,f1;
		f0=p.a[1][1],f1=p.a[2][1];
		if (t!=1 && !vi[fa[t]]) et[++wt]=fa[t],vi[fa[t]]=1;
		ef[++wf]=t;
		tr[fa[t]].a[1][2]+=f1-f[t][1],
		tr[fa[t]].a[2][1]+=min(f0,f1)-min(f[t][0],f[t][1]),
		tr[fa[t]].a[2][2]+=min(f0,f1)-min(f[t][0],f[t][1]);
		f[t][0]=f0,f[t][1]=f1;
		if (t!=1) change(1,1,n,dfn[fa[t]],tr[fa[t]]);
		t=top[fa[t]];
	}
}
signed main()
{
	tot=-1;
	memset(first,-1,sizeof(first));
	memset(nxt,-1,sizeof(nxt));
	char ch[20];
	n=read();m=read();
	scanf("%s",ch);
	for (re int i=1;i<=n;++i) v[i]=read();
	for (re int i=1;i<n;++i)
	{
		int u,v;
		u=read(),v=read();
		add_edge(u,v),add_edge(v,u);
	}
	dfs(1);
	dfs1(1,1);
	build(1,1,n);
	for (re int i=1;i<=n;++i)
	  Tr[i]=tr[i],F[i][0]=f[i][0],F[i][1]=f[i][1];
	while (m--)
	{
		wt=wf=0;
		int a,b,x,y;
		a=read(),x=read(),b=read(),y=read();
		change_path(a,x);
		change_path(b,y);	
		(min(f[1][0],f[1][1])==inf)?printf("-1\n"):printf("%lld\n",min(f[1][0],f[1][1]));
		for (re int i=1;i<=wf;++i)
		{
			int x=ef[i];
			f[x][0]=F[x][0],f[x][1]=F[x][1];
		}
		for (re int i=1;i<=wt;++i)
		{
			int x=et[i];
			vi[x]=0,tr[x]=Tr[x];
			change(1,1,n,dfn[x],tr[x]);
		}
	}
}

评测结果