NOIP 2018 왕국 수호(동적 DP)(LCT)

전송문과 동적 DP의 템플릿 차이는 수수한 트리 dp dp dp f u, 0 = ∑v f v, 1 f{u,0}=\sum_{v}f_{v,1} fu,0​=v∑​fv,1​ f u , 1 = v a l [ u ] + ∑ v m i n ( f v , 0 , f v , 1 ) f_{u,1}=val[u]+\sum_{v}min(f {v,0},f {v,1})fu,1=val[u]+v ∑min(fv,0,fv,1)령 gu,0/1g{u, 0/1} gu, 0/1은 모든 허아들의 화합 fu, 0 = g u, 0 + f s o n, 0, f u, 1 = g u, 1 + m i n(f s o n, 0, f s o n, 1) f{u,0}=g_{u,0}+f_{son,0},f_{u,1}=g_{u,1}+min(f_{son,0},f_{son,1}) fu,0​=gu,0​+fson,0​,fu,1​=gu,1​+min(fson,0​,fson,1​) ( f u , 0 , f u , 1 ) = ( f s o n , 0 , f s o n , 1 ) ∗ ( ∞ , g u , 1 g u , 0 , g u , 1 ) (f_{u,0},f_{u,1})=(f_{son,0},f_{son,1})*\binom{\infty,g_{u,1}}{g_{u,0},g_{u, 1} (fu, 0,fu, 1) = (fson, 0, fson, 1) ∗(gu, 0,gu, 1∞,gu, 1) 그리고 l c t lct lct는 허자 트리의 계수를 유지하고 a c c e s access access를 전환합니다.

#include
#define cs const
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
	while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
	return cnt * f;
}
typedef long long ll;
cs int N = 1e5 + 5;
int first[N], nxt[N << 1], to[N << 1], tot;
void add(int x, int y){
	nxt[++tot] = first[x], first[x] = tot, to[tot] = y;
}
int n, m, vl[N];
cs ll INF = 1e15;
void Mi(ll &a, ll b){ if(b < a) a = b; }
struct mat{
	ll a[2][2];
	mat(){ a[0][0] = a[0][1] = a[1][0] = a[1][1] = INF; }
	mat operator * (cs mat &A){
		mat B; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++)
			for(int k = 0; k < 2; k++) Mi(B.a[i][j], a[i][k] + A.a[k][j]);
		return B;
	}
	ll mi(){ return min(a[1][0], a[1][1]); }
	void init(ll A, ll B){ a[0][1] = a[1][1] = B; a[1][0] = A; }
};

int fa[N], ch[N][2];
mat dp[N], trans[N];
void dfs(int u, int f){
	fa[u] = f;
	ll A = 0, B = vl[u];
	for(int i = first[u]; i; i = nxt[i]){
		int t = to[i]; if(t == f) continue;
		dfs(t, u); 
		A += dp[t].a[1][1];
		B += dp[t].mi();
	} 
	trans[u].init(A, B);
	dp[u].init(A, B);
}
#define ls ch[x][0]
#define rs ch[x][1]
bool isr(int x){ return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x; }
int get(int x){ return ch[fa[x]][1] == x; }
void pushup(int x){ dp[x] = dp[rs] * trans[x] * dp[ls]; }
void rotate(int x){
	int y = fa[x], z = fa[y], k = get(x);
	if(!isr(y)) ch[z][get(y)] = x; fa[x] = z;
	ch[y][k] = ch[x][k^1]; fa[ch[x][k^1]] = y;
	ch[x][k^1] = y; fa[y] = x; pushup(y); pushup(x);
}
void splay(int x){
	while(!isr(x)){
		int y = fa[x], z = fa[y];
		if(!isr(y)) get(x) ^ get(y) ? rotate(x) : rotate(y); rotate(x);
	}
}
void access(int x){
	for(int y = 0; x; y = x, x = fa[x]){
		splay(x); 
		trans[x].a[0][1] += dp[rs].mi() - dp[y].mi();
		trans[x].a[1][1] += dp[rs].mi() - dp[y].mi();
		trans[x].a[1][0] += dp[rs].a[1][1] - dp[y].a[1][1];
		rs = y; pushup(x);
	}
}
void upt(int x, int opt, ll v){
	access(x); splay(x); 
	if(opt == 0){
		trans[x].a[0][1] += v;
		trans[x].a[1][1] += v;
	}
	else{
		trans[x].a[1][0] += v;
	} pushup(x);
}
int main(){
	n = read(), m = read(); 
	dp[0].a[0][0] = 0;
	dp[0].a[1][1] = 0;
	char opt[5]; scanf("%s", opt);
	for(int i = 1; i <= n; i++) vl[i] = read();
	for(int i = 1; i < n; i++){
		int x = read(), y = read();
		add(x, y); add(y, x);
	} dfs(1, 0);
	while(m--){
		int a = read(), x = read(), b = read(), y = read();
		upt(a, x, INF);
		upt(b, y, INF);
		splay(1);
		if(dp[1].mi() >= INF) puts("-1");
		else cout << dp[1].mi() << '
';
		upt(a, x, -INF);
		upt(b, y, -INF);
	} return 0;
}