代码

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

int n,m,c,w[100100],head[100100],f[100100][2],ct[100100],fa[100100],dp[100100],mf[100100][2];
char type[10];

struct Edge{
	int to,nxt;
}e[200200];

queue<int>change;

void read()
{
	int m1,m2;
	cin>>n>>m>>type;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&m1,&m2);
		e[++c].to=m2;
		e[c].nxt=head[m1];
		head[m1]=c;
		
		e[++c].to=m1;
		e[c].nxt=head[m2];
		head[m2]=c;
	}
}

void init(int k)
{
	int m=0x7fffffff,p;
	ct[k]=1;
	f[k][1]=w[k];
	dp[k]=dp[fa[k]]+1;
	for(int i=head[k];i;i=e[i].nxt)
	{
		if(e[i].to==fa[k])continue;
		fa[e[i].to]=k;
		init(e[i].to);
		ct[k]+=ct[e[i].to];
		f[k][1]+=min(f[e[i].to][0],f[e[i].to][1]); 
		if(f[e[i].to][1]<m)
		{
			m=f[e[i].to][1];
			p=e[i].to;
		}
		if(f[e[i].to][1]<=f[e[i].to][0] || ct[e[i].to]==1)
		{
			m=0;
			f[k][0]+=f[e[i].to][1];
		}
		else f[k][0]+=f[e[i].to][0];
	}
	if(m && m!=0x7fffffff)f[k][0]=f[k][0]-f[p][0]+f[p][1];
}

void update(int k)
{
	int m=0x7fffffff,p;
	change.push(k);
	f[k][1]=w[k];
	f[k][0]=0;
	for(int i=head[k];i;i=e[i].nxt)
	{
		if(e[i].to==fa[k])continue;
		f[k][1]+=min(f[e[i].to][0],f[e[i].to][1]); 
		if(f[e[i].to][1]<m)
		{
			m=f[e[i].to][1];
			p=e[i].to;
		}
		if(f[e[i].to][1]<=f[e[i].to][0] || ct[e[i].to]==1)
		{
			m=0;
			f[k][0]+=f[e[i].to][1];
		}
		else f[k][0]+=f[e[i].to][0];
	}
	if(m && m!=0x7fffffff)f[k][0]=f[k][0]-f[p][0]+f[p][1];
	//printf("%d#%d %d\n",k,f[k][0],f[k][1]);
}

void solve()
{
	int m1,m2,m3,m4,mm=-1;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d%d",&m1,&m2,&m3,&m4);
		mm=-1;
		if(m1==1)mm=m2;
		else if(m3==1)mm=m4;
		change.push(m1);
		f[m1][!m2]=0x3f3f3f3f;
		change.push(m3);
		f[m3][!m4]=0x3f3f3f3f;
		if(dp[m3]>dp[m1])swap(m1,m3),swap(m2,m4);
		if(dp[m1]>dp[m3])
		{
			while(dp[m1]>dp[m3])update(fa[m1]),m1=fa[m1];
		}
		while(m1!=m3)
		{
			update(fa[m1]);
			update(fa[m3]);
			m1=fa[m1];
			m3=fa[m3];
		}
		while(m1)update(fa[m1]),m1=fa[m1];
		
		if(mm!=-1)printf("%d\n",f[1][mm]<0x3f3f3f3f?f[1][mm]:-1);
		else printf("%d\n",min(f[1][0],f[1][1])<0x3f3f3f3f?min(f[1][0],f[1][1]):-1);
		while(!change.empty())
		{
			mm=change.front();change.pop();
			f[mm][0]=mf[mm][0];
			f[mm][1]=mf[mm][1];
		}
	}
}

int main()
{
	read();
	init(1);
	//for(int i=1;i<=n;i++)printf("%d#%d %d\n",i,f[i][0],f[i][1]);
	memcpy(mf,f,sizeof(f));
	solve();
} 

评测结果