LibreOJ 2955. "NOIP2018"왕국보위【동적DP】

LibreOJ 2955. "NOIP2018" 왕국 수호

역시나 누드 문제입니다. 동적 DP는 0으로 설정하고 ∞\infty∞로 설정하지 않으면 됩니다.
전이 행렬 [g x, 1 g x, 1 g x, 0 ∞]\[f v, 1 f v, 0] = [f x, 1 f x, 0]\begin{bmatrix} g{x,1} & g_{x,1}\\g_{x,0} &\infty\end{bmatrix}*\begin{bmatrix} f_{v,1}\\f_{v,0}\end{bmatrix}=\begin{bmatrix} f_{x,1}\\f_{x,0}\end{bmatrix} [gx,1​gx,0​​gx,1​∞​]∗[fv,1​fv,0​​]=[fx,1​fx,0​​]

#include
#include
#include
using namespace std;
typedef long long LL;
const int MAXN=1e5+5;const LL inf=1e17;
int n,m;LL F[MAXN][2],a[MAXN];
int cnt,Dfn[MAXN],IDfn[MAXN],Siz[MAXN],Top[MAXN],Son[MAXN],Fa[MAXN],End[MAXN];
#include
int read(){
	int ret=0;char ch=getchar();bool f=1;
	for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
	for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
	return f?ret:-ret;
}
struct Maxtin{
	LL g[2][2];
	Maxtin(){memset(g,127,sizeof(g));}
	Maxtin operator *(const Maxtin b)const{
		Maxtin c;
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		for(int k=0;k<2;k++)
		c.g[i][j]=min(c.g[i][j],g[i][k]+b.g[k][j]);
		return c;
	}
}Tre[MAXN<<2],Val[MAXN];
struct Edge{
	int tot,lnk[MAXN],nxt[MAXN<<1],son[MAXN<<1];
	void Add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
}E;
void DFS(int x,int fa){
	F[x][0]=0,F[x][1]=a[x];
	for(int j=E.lnk[x];j;j=E.nxt[j])
	if(E.son[j]!=fa){
		DFS(E.son[j],x);
		F[x][0]+=F[E.son[j]][1];
		F[x][1]+=min(F[E.son[j]][1],F[E.son[j]][0]);
	}
}
void First(int x,int fa){
	Siz[x]=1;Fa[x]=fa;
	for(int j=E.lnk[x];j;j=E.nxt[j])
	if(E.son[j]!=fa){
		First(E.son[j],x),Siz[x]+=Siz[E.son[j]];
		if(Siz[Son[x]]<Siz[E.son[j]]) Son[x]=E.son[j];
	}
}
void Second(int x,int T){
	if(Dfn[x]) return;
	Dfn[x]=++cnt,IDfn[cnt]=x,Top[x]=T,End[T]=x;
	if(!Son[x]) return;Second(Son[x],T);
	for(int j=E.lnk[x];j;j=E.nxt[j]) Second(E.son[j],E.son[j]);
}
void Build(int rt,int L,int R){
	if(L==R){
		int x=IDfn[L],g0=0,g1=a[x];
		for(int j=E.lnk[x];j;j=E.nxt[j])
		if(E.son[j]!=Fa[x]&&E.son[j]!=Son[x]) g0+=F[E.son[j]][1],g1+=min(F[E.son[j]][0],F[E.son[j]][1]);
		Tre[rt].g[1][0]=g0,Tre[rt].g[1][1]=inf,Tre[rt].g[0][0]=Tre[rt].g[0][1]=g1;Val[L]=Tre[rt];
		return;
	}
	int mid=(R+L)>>1;
	Build(rt<<1,L,mid);Build(rt<<1|1,mid+1,R);
	Tre[rt]=Tre[rt<<1]*Tre[rt<<1|1];
}
void Insert(int rt,int L,int R,int p){
	if(L==R){Tre[rt]=Val[L];return;}
	int mid=(R+L)>>1;
	if(p<=mid) Insert(rt<<1,L,mid,p);else Insert(rt<<1|1,mid+1,R,p);
	Tre[rt]=Tre[rt<<1]*Tre[rt<<1|1];
}
Maxtin Query(int rt,int L,int R,int l,int r){
	if(l<=L&&R<=r) return Tre[rt];
	int mid=(R+L)>>1;
	if(r<=mid) return Query(rt<<1,L,mid,l,r);else
	if(l>mid) return Query(rt<<1|1,mid+1,R,l,r);else
	return Query(rt<<1,L,mid,l,r)*Query(rt<<1|1,mid+1,R,l,r);
}
void Change(int x,LL f){
	Val[Dfn[x]].g[0][0]=(Val[Dfn[x]].g[0][1]+=f);
	Maxtin Now,Pre;
	while(x){
		Pre=Query(1,1,n,Dfn[Top[x]],Dfn[End[Top[x]]]);
		Insert(1,1,n,Dfn[x]);
		Now=Query(1,1,n,Dfn[Top[x]],Dfn[End[Top[x]]]);
		x=Fa[Top[x]];if(x==0) break;
		Val[Dfn[x]].g[1][0]+=Now.g[0][0]-Pre.g[0][0];
		Val[Dfn[x]].g[0][0]=(Val[Dfn[x]].g[0][1]+=min(Now.g[0][0],Now.g[1][0])-min(Pre.g[0][0],Pre.g[1][0]));
	}
}
int main(){
//	freopen("2955.in","r",stdin);
//	freopen("2955.out","w",stdout);
	n=read(),m=read();getchar(),getchar();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1,x,y;i<n;i++) x=read(),y=read(),E.Add(x,y),E.Add(y,x);
	First(1,0),Second(1,1),DFS(1,0);Build(1,1,n);
	for(int i=1;i<=m;i++){
		int x=read(),s=read(),y=read(),t=read();
		if((Fa[x]==y||Fa[y]==x)&&((s||t)==0)){printf("-1
");continue;}
		Change(x,s?-a[x]:inf-a[x]);Change(y,t?-a[y]:inf-a[y]);
		Maxtin Now=Query(1,1,n,Dfn[1],Dfn[End[1]]);
		LL Ans=min(Now.g[0][0],Now.g[1][0])+a[x]*s+a[y]*t;
		printf("%lld
",Ans);
		Change(x,s?a[x]:a[x]-inf);Change(y,t?a[y]:a[y]-inf);
	}
	return 0;
}