记录编号	586551	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]保卫王国	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.232 s
提交时间	2024-02-03 11:00:26	内存使用	36.71 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//DDP
const int N = 2e5+10;
const ll inf = 1e10;
int n,m;
struct Matrix{
	ll a,b,c,d;
	Matrix operator * (Matrix x){
		Matrix y;
		y.a = min(a+x.a,b+x.c);
		y.b = min(a+x.b,b+x.d);
		y.c = min(c+x.a,d+x.c);
		y.d = min(c+x.b,d+x.d); 
		return y;
	}
}I,val[N<<2],G[N];

struct mad{
	int ver,nx,ed;
}e[N<<1];
ll hd[N],tot,a[N],cnt;
void add(int x,int y){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}

int size[N],son[N],fa[N],en[N];
ll dfn[N],rnk[N],top[N],f[N][2],g[N][2];
void dfs1(int x){
	size[x] = 1,f[x][1] = a[x],f[x][0] = 0;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa[x])continue;
		fa[y] = x;dfs1(y);
		size[x] += size[y],f[x][1] += min(f[y][1],f[y][0]),f[x][0] += f[y][1];
		if(!son[x] || size[y] > size[son[x]])son[x] = y;
	}
}
void dfs2(int x,int t){
	dfn[x] = ++cnt,rnk[cnt] = x,top[x] = t;
	g[x][1] = a[x],g[x][0] = 0;
	if(son[x])dfs2(son[x],t),en[x] = en[son[x]];
	else en[x] = x;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa[x] || y == son[x])continue;
		dfs2(y,y);
		g[x][1] += min(f[y][1],f[y][0]),g[x][0] += f[y][1];
	}
}

struct segtree{
	void pushup(int p){
		val[p] = val[p<<1|1] * val[p<<1];
	}
	void build(int p,int l,int r){
		if(l == r){
			val[p] = G[rnk[l]]; 
			return;
		}
//		cout<<p<<' '<<l<<' '<<r<<endl;
		int mid = l + r >> 1;
		build(p<<1,l,mid),build(p<<1|1,mid+1,r);
		pushup(p);
	}
	void modify(int p,int l,int r,int x){
		if(l == r)return val[p] = G[rnk[l]],void();
		int mid = l + r >> 1;
		if(x <= mid)modify(p<<1,l,mid,x);
		else modify(p<<1|1,mid+1,r,x);
		pushup(p);
	}
	Matrix ask(int p,int l,int r,int L,int R){
		if(L <= l && r <= R)return val[p];
		int mid = l + r >> 1;
		if(R <= mid)return ask(p<<1,l,mid,L,R);
		else if(L > mid)return ask(p<<1|1,mid+1,r,L,R);
		else return ask(p<<1|1,mid+1,r,L,R) * ask(p<<1,l,mid,L,R); 
	}
}T;
void update(int x){
	G[x].b = G[x].d = g[x][1],G[x].a = inf,G[x].c = g[x][0]; 
}
ll cal(int x,ll z){
	g[x][1] += z;
	while(top[x] != 1){
		int fx = top[x],ff = fa[fx];
		Matrix s1 = I * T.ask(1,1,n,dfn[fx],dfn[en[fx]]);
		update(x),T.modify(1,1,n,dfn[x]);
		Matrix s2 = I * T.ask(1,1,n,dfn[fx],dfn[en[fx]]);
		g[ff][1] += min(s2.a,s2.b) - min(s1.a,s1.b);
		g[ff][0] += s2.b - s1.b;
		x = ff;
	}
	update(x),T.modify(1,1,n,dfn[x]);
	Matrix s = I * T.ask(1,1,n,1,dfn[en[1]]);
	return min(s.a,s.b);
}
void solve(int x,int y,int v1,int v2){
	if(!v1 && !v2 && (fa[x] == y || fa[y] == x)){printf("-1\n");return;}
	ll ans = 0;
	cal(x,v1?-inf:inf);
	ans = cal(y,v2?-inf:inf);
	if(v1)ans += inf;if(v2)ans += inf; 
	printf("%lld\n",ans);
	cal(x,v1?inf:-inf),cal(y,v2?inf:-inf);
}
int main(){
	freopen("2018defense.in","r",stdin);
	freopen("2018defense.out","w",stdout);
	scanf("%d%d",&n,&m);
	char c[10];cin>>c;
	for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
	for(int i = 1;i < n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i = 1;i <= n;i++)update(i);
	T.build(1,1,n);
	for(int i = 1;i <= m;i++){
		int x,y,v1,v2;
		scanf("%d%d%d%d",&x,&v1,&y,&v2);
		solve(x,y,v1,v2);
	}
	

	return 0;
	
}