题面

大秦为你打开题目传送门

题目描述

Z 国有 $n$ 座城市，$(n - 1)$ 条双向道路，每条双向道路连接两座城市，且任意两座城市都能通过若干条道路相互到达。

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

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

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

输入格式

第一行有两个整数和一个字符串，依次表示城市数 $n$，要求数 $m$ 和数据类型 $type$。$type$ 是一个由大写字母 A，B 或 C 和一个数字 1，2，3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中 有具体的描述。

第二行有 $n$ 个整数，第 $i$ 个整数表示编号 $i$ 的城市中驻扎军队的花费 $p_i$。

接下来 $(n - 1)$ 行，每行两个整数 $u,v$，表示有一条 $u$ 到 $v$ 的双向道路。

接下来 $m$ 行，每行四个整数 $a, x, b, y$，表示一个要求是在城市 $a$ 驻扎 $x$ 支军队，在城市 $b$ 驻扎 $y$ 支军队。其中，$x,y$ 的取值只有 $0$ 或 $1$：

  • 若 $x$ 为 $0$，表示城市 $a$ 不得驻扎军队。
  • 若 $x$ 为 $1$，表示城市 $a$ 必须驻扎军队。
  • 若 $y$ 为 $0$，表示城市 $b$ 不得驻扎军队。
  • 若 $y$ 为 $1$，表示城市 $b$ 必须驻扎军队。

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

输出格式

输出共 $m$ 行，每行包含一个个整数，第 $j$ 行表示在满足国王第 $j$ 个要求时的最小开销， 如果无法满足国王的第 $j$ 个要求，则该行输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
12 
7 
-1

提示

样例 1 解释

  • 对于第一个要求，在 $4$ 号和 $5$ 号城市驻扎军队时开销最小。
  • 对于第二个要求，在 $1$ 号、$2$ 号、$3$ 号城市驻扎军队时开销最小。
  • 第三个要求是无法满足的，因为在 $1$ 号、$5$ 号城市都不驻扎军队就意味着由道路直接连 接的两座城市中都没有驻扎军队。

数据规模与约定

测试点编号 $\text{type}$ $n = m=$
$1,2$ A3 $10$
$3,4$ C3 $10$
$5,6$ A3 $100$
$7$ C3 $100$
$8,9$ A3 $2\times 10^3$
$10,11$ C3 $2\times 10^3$
$12,13$ A1 $10^5$
$14, 15, 16$ A2 $10^5$
$17$ A3 $10^5$
$18,19$ B1 $10^5$
$20,21$ C1 $10^5$
$22$ C2 $10^5$
$23, 24, 25$ C3 $10^5$

数据类型的含义：

  • A：城市 $i$ 与城市 $i + 1$ 直接相连。
  • B：任意城市与城市 $1$ 的距离不超过 $100$（距离定义为最短路径上边的数量），即如果这 棵树以 $1$ 号城市为根，深度不超过 $100$。
  • C：在树的形态上无特殊约束。
  • 1：询问时保证 $a = 1,x = 1$，即要求在城市 $1$ 驻军。对 $b,y$ 没有限制。
  • 2：询问时保证 $a,b$ 是相邻的（由一条道路直接连通）
  • 3：在询问上无特殊约束。

对于 $100\%$的数据，保证 $1 \leq n,m ≤ 10^5$，$1 ≤ p_i ≤ 10^5$，$1 \leq u, v, a, b \leq n$，$a \neq b$，$x, y \in \{0, 1\}$。

思路

思维初探：暴力做法

对于前 11 个数据点，$n,m$ 都特别小，我们完全可以对于每一个询问做一次 DP 。

不妨设置 $dp[i][0/1]$ 表示这个点选 ( 1 ) 或者不选 ( 0 ) 的价值。那么不难想到转移方程式子：

如果想要一个节点选或者不选，只需要让他的权值变成 0 或者 极大值即可。

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
namespace Sub1 {
    ll dp[N][2];
    inline void Dfs(int u, int fa) {
        dp[u][0] = 0;
        dp[u][1] = a[u];
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(v == fa) continue;
            Dfs(v, u);
            dp[u][0] += dp[v][1];
            dp[u][1] += min(dp[v][0], dp[v][1]);
        }
    }
    inline void Work() {
        int u, x, v, y;
        while(Q--) {
            read(u, x, v, y);
            ll au = a[u], av = a[v];
            if(x == 0) a[u] = 1e9;
            else a[u] = 0;
            if(y == 0) a[v] = 1e9;
            else a[v] = 0;
            Dfs(1, 0);
            if(min(dp[1][0], dp[1][1]) >= 1e9) {
                puts("-1");
            }
            else {
                printf("%lld\n", min(dp[1][0], dp[1][1]) + x * au + y * av);
            }
            a[u] = au, a[v] = av;
        }
    }
};

侧面突破：链上做法

观察数据点，有 $24\ \tt pts$ 的链上做法。我们考虑链上的做法，其实链就是一个区间，所以说链上的做法就不难想到线段树。我们定义线段树上的一个节点存储一个矩阵：

这个矩阵每一个元素表示当前结点的左端点（第一个元素）取（1）或者不取（0）、右端点（第二个元素）取（1）或者不取（0）的最小值。

合并的时候分别讨论即可。

正解思路：倍增合并

我们发现，如果要从链进化成树，可以用倍增的思想变成一段一段的然后合并，这时倍增维护的东西应当是和线段树一样的，然后我们考虑如何计算答案。

首先基础的，我们需要两个数组 $f[i][0/1]$ 和 $g[i][0/1]$ 分别表示当前这个点选或者不选这个点的子树的最小方案、还有这棵树挖掉以这个点为子树之后这个点选不选的最小方案。

我们设定数组 $dp[i][j][0/1][0/1]$ 表示：节点 $i$ 到节点 $i$ 的 $2^j$ 个祖先的路径上，$i$ 节点选或不选（1/0）$i$ 节点的 $2^j$ 个父亲选或不选的最小方案

然后有了这些数组我们就可以处理询问了。

  • 如果 $a$ 是 $b$ 的祖先，那么可以直接倍增上去（还是像 $dp$ 一样合并倍增数组，枚举中间点的状态即可），然后不要忘了加上 $g[a][x]$ 。
  • 否则我们需要先把 $a$ 和 $b$ 都倍增到 $lca$ 的儿子处，然后枚举 $lca$ 和两个儿子的状态，具体可以见代码。
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
// #pragma GCC optimize(2)
// #pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;
const ll INF = (1LL << 60);

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, Q;
int a[N];
Graph< N, N << 1 >G;

set<pair<int , int > >st;

int fa[N][20];
int dep[N];

ll f[N][2], g[N][2];
ll dp[N][20][2][2];

inline void Input() {
    char type[10];
    scanf("%d%d%s", &n, &Q, &type);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    int u, v;
    for(int i = 1; i < n; i++) {
        read(u, v);
        G.AddEdge(u, v);
        G.AddEdge(v, u);
        st.insert(make_pair(u, v));
        st.insert(make_pair(v, u));
    }
}

inline void Dfs1(int u, int FA) {
    dep[u] = dep[FA] + 1;
    f[u][1] = a[u];
    fa[u][0] = FA;
    for(int i = 1; i < 20; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == FA) continue;
        Dfs1(v, u);
        f[u][0] += f[v][1];
        f[u][1] += min(f[v][0], f[v][1]);
    }
}
inline void Dfs2(int u) {
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa[u][0]) continue;
        g[v][0] = g[u][1] + f[u][1] - min(f[v][0], f[v][1]);
        g[v][1] = min(g[u][0] + f[u][0] - f[v][1], g[v][0]);
        Dfs2(v);
    }
}

inline ll Calc(int u, int x, int v, int y) {
    if(dep[u] < dep[v]) swap(u, v), swap(x, y);

    ll tx[2] = {INF, INF}, ty[2] = {INF, INF};
    ll nx[2], ny[2];
    // cout << 1 << endl;
    tx[x] = f[u][x], ty[y] = f[v][y];
    // cout << 1 << endl;
    for(int i = 19; i >= 0; i--) {
        if(dep[fa[u][i]] >= dep[v]){
            nx[0] = nx[1] = INF;
            for(int j = 0; j < 2; j++) {
                for(int k = 0; k < 2; k++) {
                    nx[j] = min(nx[j], tx[k] + dp[u][i][k][j]);
                }
            }
            tx[0] = nx[0], tx[1] = nx[1];
            u = fa[u][i];
        }
    }
    // cout << 2 << endl;
    if(u == v) return tx[y] + g[u][y];
    for(int i = 19; i >= 0; i--) {
        if(fa[u][i] != fa[v][i]){
            nx[0] = nx[1] = INF;
            ny[0] = ny[1] = INF;
            for(int j = 0; j < 2; j++) {
                for(int k = 0; k < 2; k++) {
                    nx[j] = min(nx[j], tx[k] + dp[u][i][k][j]);
                    ny[j] = min(ny[j], ty[k] + dp[v][i][k][j]);
                }
            }
            tx[0] = nx[0], tx[1] = nx[1];
            u = fa[u][i];
            ty[0] = ny[0], ty[1] = ny[1];
            v = fa[v][i];
        }
    }
    // cout << 3 << endl;
    int lca = fa[u][0];
    ll ans0 = f[lca][0] - f[u][1] - f[v][1] + tx[1] + ty[1] + g[lca][0];
    ll ans1 = f[lca][1] - min(f[u][0], f[u][1]) - min(f[v][0], f[v][1]) + min(tx[0], tx[1]) + min(ty[0], ty[1]) + g[lca][1];
    return min(ans0, ans1);
}

inline void Work() {
    Dfs1(1, 0), Dfs2(1);
    for(int i = 1; i <= n; i++) {
        dp[i][0][0][0] = INF;
        dp[i][0][0][1] = f[fa[i][0]][1] - min(f[i][0], f[i][1]);
        dp[i][0][1][0] = f[fa[i][0]][0] - f[i][1];
        dp[i][0][1][1] = f[fa[i][0]][1] - min(f[i][0], f[i][1]);
    }
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n; i++) {
            for(int mk = 0; mk < 4; mk++) {
                int u = mk / 2, v = mk % 2;
                dp[i][j][u][v] = INF;
                for(int w = 0; w < 2; w++) {
                    dp[i][j][u][v] = min(dp[i][j][u][v], dp[i][j - 1][u][w] + dp[fa[i][j - 1]][j - 1][w][v]);
                }
            }
        }
    }
    int u, x, v, y;
    while(Q--) {
        read(u, x, v, y);
        if(x == 0 && y == 0 && st.find(make_pair(u, v)) != st.end()) {
            printf("-1\n");
            continue;
        }
        printf("%lld\n", Calc(u, x, v, y));
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}