代码

#include<algorithm>
#include<cstdio>
#define mxn 131072
#define LL long long
using namespace std;
const LL inf=1e12;
int n,m,sl,fh,val[mxn];
int siz[mxn],son[mxn];
LL g[mxn][2];
int t,h[mxn];
struct Tre
{
	int to,nxt;
}e[mxn<<1];
struct Martix
{
	LL s[2][2];
	inline Martix() {s[0][0]=s[0][1]=s[1][0]=s[1][1]=inf;}
	inline LL* operator [](const int &x) {return s[x];}
};
inline Martix operator *(const Martix &a,const Martix &b)
{
	Martix c;
	c.s[0][0]=min(a.s[0][0]+b.s[0][0],a.s[0][1]+b.s[1][0]);
	c.s[0][1]=min(a.s[0][0]+b.s[0][1],a.s[0][1]+b.s[1][1]);
	c.s[1][0]=min(a.s[1][0]+b.s[0][0],a.s[1][1]+b.s[1][0]);
	c.s[1][1]=min(a.s[1][0]+b.s[0][1],a.s[1][1]+b.s[1][1]);
	return c;
}
struct Bst
{
	int rt,top,stk[mxn],vis[mxn],lsiz[mxn];
	Martix w[mxn],f[mxn];
	struct Tree
	{
		int l,r,fa;
		Tree() {fa=l=r=0;}
	}tr[mxn];
	inline Bst() {w[0][0][0]=w[0][1][1]=f[0][0][0]=f[0][1][1]=0;}
	inline void init() {for(int i=1;i<=n;++i) w[i][1][0]=g[i][0],w[i][0][0]=w[i][0][1]=g[i][1];}
	inline void upd(int u) {f[u]=f[tr[u].l]*w[u]*f[tr[u].r];}
	inline bool isrt(int u) {return (tr[tr[u].fa].l!=u)&&(tr[tr[u].fa].r!=u);}
	int build(int l,int r)
	{
		if(l>r) return 0;
		int tot=0;
		for(int i=l;i<=r;++i) tot+=lsiz[stk[i]];
		for(int i=l,x=lsiz[stk[i]];i<=r;++i,x+=lsiz[stk[i]])
			if(x*2>=tot)
			{
				x=stk[i];tr[x].l=build(l,i-1);tr[x].r=build(i+1,r);
				tr[tr[x].l].fa=x;tr[tr[x].r].fa=x;upd(x);return x;
			}
	}
	int build(int x)
	{
		for(int i=x;i;i=son[i]) vis[i]=1;
		for(int v,u=x;u;u=son[u])
			for(int i=h[u];i;i=e[i].nxt)
				if(!vis[v=e[i].to])
					tr[build(v)].fa=u;
		top=0;for(int i=x;i;i=son[i]) stk[++top]=i,lsiz[i]=siz[i]-siz[son[i]];
		return build(1,top);
	}
	inline void change(int x,LL v1,LL v2)
	{
		w[x][1][0]+=v1;
		w[x][0][0]=(w[x][0][1]+=v2);
		for(int v;x;x=v)
			if((v=tr[x].fa)&&isrt(x))
			{
				w[v][0][1]=(w[v][0][0]-=min(f[x][0][0],f[x][1][0]));
				w[v][1][0]-=f[x][0][0];upd(x);
				w[v][0][1]=(w[v][0][0]+=min(f[x][0][0],f[x][1][0]));
				w[v][1][0]+=f[x][0][0];
			}
			else upd(x);
	}
}T;
inline char gc()
{
	static char buf[1<<20],*S,*T;
	if(S==T){T=(S=buf)+fread(buf,1,1<<20,stdin);if(S==T)return EOF;}
	return *S++;
}
inline int rd()
{
	sl=0;fh=1;
	char ch=gc();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=gc();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=gc();
	return sl*fh;
}
inline void add(int u,int v)
{
	e[++t]=(Tre){v,h[u]};h[u]=t;
	e[++t]=(Tre){u,h[v]};h[v]=t;
}
void dfs1(int u,int f)
{
	int v;siz[u]=1;g[u][1]=val[u];
	for(int i=h[u];i;i=e[i].nxt)
		if((v=e[i].to)!=f)
		{
			dfs1(v,u);siz[u]+=siz[v];
			if(siz[v]>siz[son[u]]) son[u]=v;
			g[u][1]+=min(g[v][0],g[v][1]);
			g[u][0]+=g[v][1];
		}
}
void dfs2(int u,int f)
{
	if(!son[u]) return ;
	g[u][1]-=min(g[son[u]][0],g[son[u]][1]);
	g[u][0]-=g[son[u]][1];
	int v;
	for(int i=h[u];i;i=e[i].nxt)
		if((v=e[i].to)!=f)
			dfs2(v,u);
}
int main()
{
	n=rd();m=rd();rd();int a,b,x,y;LL ans;
	for(int i=1;i<=n;++i) val[i]=rd();
	for(int i=1;i<n;++i) x=rd(),y=rd(),add(x,y);
	dfs1(1,0);dfs2(1,0);T.init();T.rt=T.build(1);
	while(m--)
	{
		a=rd();x=rd();b=rd();y=rd();
		T.change(a,inf*x,inf*(!x));
		T.change(b,inf*y,inf*(!y));
		ans=min(T.f[T.rt][0][0],T.f[T.rt][1][0]);
		if(ans<inf) printf("%lld\n",ans);
		else puts("-1");
		T.change(a,-inf*x,-inf*(!x));
		T.change(b,-inf*y,-inf*(!y));
	}
	return 0;
}

评测结果