「LOJ2955」「NOIP2018」保卫王国

Description

Z 国有 nn 座城市,n1n-1 条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:

  • 一座城市可以驻扎一支军队,也可以不驻扎军队。
  • 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
  • 在城市里驻扎军队会产生花费,在编号为 ii 的城市中驻扎军队的花费是 pip_i

小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了 mm 个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第 jj 个要求能够满足上述驻扎条件(不需要考虑第 jj 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 jj 个要求无法满足,则需要输出 1-1。现在请你来帮助小 Z。

Input

输入文件名为 defense.in
第一行包含两个正整数 n,mn,m 和一个字符串 type\text{type},分别表示城市数、要求数和数据类型。type\text{type} 是一个由大写字母 ABC 和一个数字 112233 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在「数据范围与提示」中有具体的描述。
第二行 nn 个整数 pip_i,表示编号 ii 的城市中驻扎军队的花费。
接下来 n1n-1 行,每行两个正整数 u,vu,v,表示有一条 uuvv 的双向道路。
接下来 mm 行,第 jj 行四个整数 a,x,b,ya,x,b,y,表示第 jj 个要求是在城市 aa 驻扎 xx 支军队,在城市 bb 驻扎 yy 支军队。其中,x,yx,y 的取值只有 0011:若 xx00,表示城市 aa 不得驻扎军队,若 xx11,表示城市 aa 必须驻扎军队;若 yy00,表示城市 bb 不得驻扎军队,若 yy11,表示城市 bb 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。

Output

输出文件名为 defense.out
输出共 mm 行,每行包含一个整数,第 jj 行表示在满足国王第 jj 个要求时的最小开销,如果无法满足国王的第 jj 个要求,则该行输出 1-1

Sample Input

1
2
3
4
5
6
7
8
9
5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0

Sample Output

1
2
3
12
7
-1

HINT

对于第一个要求,在 44 号和 55 号城市驻扎军队时开销最小。

对于第二个要求,在 11 号、22 号、33 号城市驻扎军队时开销最小。

第三个要求是无法满足的,因为在 11 号、55 号城市都不驻扎军队就意味着由道路直接连接的两座城市中都没有驻扎军队。
对于全部数据,n=m105,1pi105n=m\le 10^5,1\le p_i\le 10^5

Solution

动态dp题。
fi,0f_{i,0}表示子树ii之内,且ii不驻扎军队的的最小花费。
fi,1f_{i,1}表示子树ii之内,且ii驻扎军队的最小花费
由题意得到:
fi,0=fj,1f_{i,0}=\sum f_{j,1}jjii的儿子)
fi,1=min{fj,0,fj,1}f_{i,1}=\sum \min\{f_{j,0},f_{j,1}\}
然后考虑动态dp
对于同一条重链上的点,从下到上考虑。
fi,0=fi1,1+gi,0f_{i,0}=f_{i-1,1}+g_{i,0}
fi,1=min{fi1,0+gi,1,fi1,1+gi,1}f_{i,1}=\min\{f_{i-1,0}+g_{i,1},f_{i-1,1}+g_{i,1}\}
其中gi,1g_{i,1}表示ii点驻扎军队,加上min{fj,0,fj,1}\sum \min\{f_{j,0},f_{j,1}\},这里的jj不是ii的重儿子。
同理gi,0g_{i,0}表示ii点不驻扎的其他儿子最后代价之和。
这显然满足矩阵递推的。
每一次修改的时候修改链头的父亲的gg数组就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e5 + 6;
char tmp[6];
ll v[N];
int head[N], en;
struct Matrix {
ll a[2][2];
Matrix() {for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) a[i][j] = 1e11;}
Matrix operator * (const Matrix b) {
Matrix c;
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
return c;
}
};
void show(Matrix);
Matrix val[N];
int id[N], num, tra[N];
struct Tree {
Matrix t[N * 4];
int ls[N * 4], rs[N * 4];
#define lch (o<<1)
#define rch (o<<1|1)
void up(int o) {
t[o] = t[rch] * t[lch];
}
void build(int o, int l, int r) {
ls[o] = l, rs[o] = r;
if(l == r) {
t[o] = val[tra[l]];
return;
}
int mid = (l + r) >> 1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
up(o);
}
void ins(int o, int x, Matrix &v) {
if(ls[o] == rs[o]) {
t[o] = v;
return;
}
int mid = (ls[o] + rs[o]) >> 1;
if(x <= mid) ins(lch, x, v);
else ins(rch, x, v);
up(o);
}
Matrix query(int o, int l, int r) {
if(l <= ls[o] && r >= rs[o]) return t[o];
int mid = (ls[o] + rs[o]) >> 1;
if(r <= mid) return query(lch, l, r);
if(l > mid) return query(rch, l, r);
return query(rch, l, r) * query(lch, l, r);
}
}t;
struct Edge {
int u, v, nxt;
}e[N * 2];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
ll f[N][2];
int siz[N], son[N], fa[N];
int top[N];
void dfs1(int x, int F) {
siz[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs1(y, x);
siz[x] += siz[y];
fa[y] = x;
if(siz[y] > siz[son[x]]) son[x] = y;
}
}
int End[N];
void dfs2(int x, int F) {
id[x] = ++num;
tra[num] = x;
top[x] = F;
End[top[x]] = id[x];
f[x][1] = v[x];
val[x].a[0][1] = v[x];
val[x].a[1][0] = 0;
if(son[x]) {
int y = son[x];
dfs2(son[x], F);
f[x][0] += f[y][1];;
f[x][1] += min(f[y][0], f[y][1]);
}
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == son[x] || y == fa[x]) continue;
dfs2(y, y);
f[x][0] += f[y][1];
f[x][1] += min(f[y][0], f[y][1]);
val[x].a[0][1] += min(f[y][0], f[y][1]);
val[x].a[1][0] += f[y][1];
}
val[x].a[1][1] = val[x].a[0][1];
}
void update(int x, ll w) {
Matrix bef, aft;
val[x].a[0][1] += w - v[x];
val[x].a[1][1] += w - v[x];
v[x] = w;
while(x) {
bef = t.query(1, id[top[x]], End[top[x]]);
t.ins(1, id[x], val[x]);
aft = t.query(1, id[top[x]], End[top[x]]);

x = fa[top[x]];
val[x].a[0][1] += min(aft.a[1][0], aft.a[1][1]) - min(bef.a[1][0], bef.a[1][1]);
val[x].a[1][0] += aft.a[1][1] - bef.a[1][1];
val[x].a[1][1] = val[x].a[0][1];
}
}

int main() {
int n = read(), m = read();
scanf("%s", tmp);
for(int i = 1; i <= n; ++i) v[i] = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
t.build(1, 1, n);
Matrix ans;
for(int i = 1; i <= m; ++i) {
int a = read();
ll x = read();
int b = read();
ll y = read();
int tx = v[a];
int ty = v[b];
x = (x == 0 ? 1e11 : -1e11);
y = (y == 0 ? 1e11 : -1e11);
update(a, x + tx);
update(b, y + ty);
ans = t.query(1, id[1], End[1]);
ll res = min(ans.a[1][0], ans.a[0][1]);
res = min(res, min(ans.a[0][0], ans.a[1][1]));
if(res >= 1e11) puts("-1");
else if(res < 0) {
if(x < tx && y < ty) writeln(res + 2e11);
else writeln(res + 1e11);
} else writeln(res);
update(a, tx);
update(b, ty);
}
return 0;
}