C++14(g++5.4) 解法, 执行用时: 1319ms, 内存消耗: 21400K, 提交时间: 2019-11-15 15:10:43

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define inf (1ll<<50)
#define ll long long
using namespace std;
int n,m,t;
int first[N],v[N<<1],nxt[N<<1];
int fa[N],Fa[N],son[N][2];
ll A[N],f[N][2];
void add(int x,int y){
	nxt[++t]=first[x],first[x]=t,v[t]=y;
}
struct matrix{
	ll m[2][2];
	matrix()  {m[0][0]=m[0][1]=m[1][0]=m[1][1]=inf;}
	friend matrix operator*(const matrix &A,const matrix &B){
		matrix C;
		for(int i=0;i<2;++i)
			for(int k=0;k<2;++k)
				for(int j=0;j<2;++j)
					C.m[i][j]=min(C.m[i][j],A.m[i][k]+B.m[k][j]);
		return C;
	}
}val[N],T[N];
void dp(int x){
	f[x][1]=A[x],f[x][0]=0;
	for(int i=first[x];i;i=nxt[i]){
		int to=v[i];
		if(to==fa[x])  continue;
		fa[to]=Fa[to]=x,dp(to);
		f[x][1]+=min(f[to][0],f[to][1]);
		f[x][0]+=f[to][1];
	}
	val[x].m[1][0]=f[x][0];
	val[x].m[0][0]=val[x].m[0][1]=f[x][1];
	T[x]=val[x];
}
namespace LCT{
	bool Get(int x)  {return son[fa[x]][1]==x;}
	bool isroot(int x)  {return (!fa[x])||(son[fa[x]][0]!=x&&son[fa[x]][1]!=x);}
	void update(int x){
		T[x]=val[x];
		if(son[x][0])  T[x]=T[son[x][0]]*T[x];
		if(son[x][1])  T[x]=T[x]*T[son[x][1]];
	}
	void Rotate(int x){
		int y=fa[x],z=fa[y];
		int k=Get(x),l=son[x][k^1];
		son[y][k]=l,fa[l]=(l?y:0);
		if(!isroot(y))  son[z][Get(y)]=x;fa[x]=z;
		son[x][k^1]=y,fa[y]=x;
		update(y),update(x);
	}
	void Splay(int x){
		while(!isroot(x)){
			int y=fa[x];
			if(!isroot(y))  Rotate(Get(x)==Get(y)?y:x);
			Rotate(x);
		}
	}
	void Access(int x){
		for(int i=0;x;x=fa[i=x]){
			Splay(x);
			if(son[x][1]){
				val[x].m[1][0]+=T[son[x][1]].m[0][0];
				val[x].m[0][0]+=min(T[son[x][1]].m[0][0],T[son[x][1]].m[1][0]);
			}
			if(i){
				val[x].m[1][0]-=T[i].m[0][0];
				val[x].m[0][0]-=min(T[i].m[0][0],T[i].m[1][0]);
			}
			val[x].m[0][1]=val[x].m[0][0];
			son[x][1]=i,update(x);
		}
	}
	void Modify(int x,ll y){
		Access(x),Splay(x);
		val[x].m[0][0]+=y,val[x].m[0][1]+=y;
		update(x);
	}
	ll Query(){
		Splay(1);
		return min(T[1].m[0][0],T[1].m[1][0]);
	}
}
using namespace LCT;
char S[5];
void solve(int u,int x,int v,int y){
	if(!x&&!y&&(Fa[u]==v||Fa[v]==u))  {puts("-1");return;}
	Modify(u,x?-inf:inf),Modify(v,y?-inf:inf);
	printf("%lld\n",Query()+inf*(x+y));
	Modify(u,x?inf:-inf),Modify(v,y?inf:-inf);
}
int main(){
	int x,y,a,b;
	scanf("%d%d%s",&n,&m,S);
	for(int i=1;i<=n;++i)  scanf("%d",&A[i]);
	for(int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dp(1);
	while(m--){
		scanf("%d%d%d%d",&a,&x,&b,&y),solve(a,x,b,y);
	}
	return 0;
}

C++ 解法, 执行用时: 499ms, 内存消耗: 17916K, 提交时间: 2022-04-23 10:17:26

#include<bits/stdc++.h>
using namespace std;
const long long NN=100004,INF=1e15;
struct node
{
	long long a,b,c,d;
	node(){}
	node(const long long &_a,const long long &_b,const long long &_c,const long long &_d){a=_a,b=_b,c=_c,d=_d;}
}f[NN],g[NN];
node operator*(const node&a,const node&b)
{
	return node(max(a.a+b.a,a.b+b.c),max(a.a+b.b,a.b+b.d),max(a.c+b.a,a.d+b.c),max(a.c+b.b,a.d+b.d));
}
int ch[NN][2],fa[NN],e[NN],dis[NN<<1],nxt[NN<<1],tot;
long long dp[NN][2],w[NN];
void add(int a,int b)
{
	nxt[++tot]=e[a];
	e[a]=tot;
	dis[tot]=b;
}
void dfs(int x)
{
	dp[x][1]=w[x];
	for(int i=e[x];i;i=nxt[i])
	{
		if(fa[x]==dis[i])
			continue;
		fa[dis[i]]=x;
		dfs(dis[i]);
		dp[x][1]+=dp[dis[i]][0];
		dp[x][0]+=max(dp[dis[i]][0],dp[dis[i]][1]);
	}
	f[x]=g[x]=node(dp[x][0],dp[x][0],dp[x][1],-INF);
}
bool in(int x)
{
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void up(int x)
{
	f[x]=g[x];
	if(ch[x][0])
		f[x]=f[ch[x][0]]*f[x];
	if(ch[x][1])
		f[x]=f[x]*f[ch[x][1]];
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],o=ch[y][1]==x;
	if(!in(y))
		ch[z][y==ch[z][1]]=x;
	fa[x]=z;
	ch[y][o]=ch[x][!o];
	fa[ch[x][!o]]=y;
	ch[x][!o]=y;
	fa[y]=x;up(y);
}
void splay(int x)
{
	int y,z;
	while(!in(x))
	{
		y=fa[x];
		z=fa[y];
		if(!in(y))
			rotate(((x==ch[y][0])==(y==ch[z][0]))?y:x);
		rotate(x);
	}
	up(x);
}
void access(int x)
{
	for(int y=0;x;x=fa[y=x])
	{
		splay(x);
		if(ch[x][1])
		{
			g[x].a+=max(f[ch[x][1]].a,f[ch[x][1]].c);
			g[x].c+=f[ch[x][1]].a;
		}
		if(y)
		{
			g[x].a-=max(f[y].a,f[y].c);
			g[x].c-=f[y].a;
		}
		g[x].b=g[x].a;
		ch[x][1]=y;
		up(x);
	}
}
void update(int x,long long sum)
{
	access(x);
	splay(x);
	g[x].c+=sum,up(x);
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,m;
	long long sum=0;
	string s;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
		sum+=w[i];
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1);
	while(m--)
	{
		int a,x,b,y;
		cin>>a>>x>>b>>y;
		update(a,x?-INF:INF);
		update(b,y?-INF:INF);
		splay(1);
		long long ans=sum-max(f[1].a,f[1].c)+(2-x-y)*INF;
		if(ans>INF)
			cout<<-1<<endl;
		else
			cout<<ans<<endl;
		update(a,x?INF:-INF);
		update(b,y?INF:-INF);
	}
	return 0;
}