[noip2018-提高] 保卫王国

GitHub跳转原题关系图返回列表

树上带权顶点覆盖：换根 DP 拆出 LCA 上下两部分，倍增合并路径 2x2 min-plus 转移矩阵，单次询问 O(log n)。

OJ: roj

题目 ID: 3663

难度:提高+/省选-

标签:

创建: 2026-10-02 14:16

更新: 2026-10-10 11:30

形式化题目

给定 $n$ 个结点的一棵树，结点 $i$ 驻军的花费为 $p_i$ 。需要选出一个结点集合 $S$ （驻军方案），使得树上每条边至少有一个端点属于 $S$ ，即树的带权顶点覆盖；目标是最小化 $\sum_{i \in S} p_i$ 。

有 $m$ 个互相独立的询问。第 $j$ 个询问给出两个不同的结点 $a, b$ 以及两个取值 $x, y \in \{0, 1\}$ ：强制 $a$ 的驻军状态为 $x$ （ $1$ 必须驻军， $0$ 不得驻军）、 $b$ 的状态为 $y$ ，只在这一个约束下求最小开销；若该约束与"每条边至少一端驻军"冲突，则输出 $-1$ 。

正解

思路

朴素做法。 树形 DP 一次就能算出无约束的最小开销：设 $f_0(u)$ 、 $f_1(u)$ 分别表示结点 $u$ 不驻军 / 驻军时其子树的最小开销，子结点集合为 $ch(u)$ ，则

f_0(u)=\sum_{v \in ch(u)} f_1(v), \qquad f_1(u)=p_u+\sum_{v \in ch(u)} \min\bigl(f_0(v), f_1(v)\bigr).

直观理解： $u$ 不驻军时，边 $(u,v)$ 只能靠 $v$ 覆盖， $v$ 必须驻军； $u$ 驻军时边 $(u,v)$ 已被覆盖， $v$ 可以自由取小。整个 DP 是 $O(n)$ 的。

把询问的约束拆到路径上。 对一次询问，设 $c = \operatorname{LCA}(a, b)$ 。强制 $a$ 、 $b$ 的状态后，受影响的部分只有三块：

路径 $a \to c$ （不含 $c$ ）；
路径 $b \to c$ （不含 $c$ ）；
$c$ 自身的悬挂子树与 $c$ 以上的整棵树，这部分只依赖 $c$ 的状态。

第 3 块可以用换根 DP 预处理。记 $\operatorname{con}(v, s)$ 为"父结点状态为 $s$ 时子树 $v$ 的贡献"：

\operatorname{con}(v, s) = \begin{cases} \min(f_0(v), f_1(v)) & s = 1 \\ f_1(v) & s = 0 \end{cases}

设 $g_s(u)$ 为除 $u$ 的子树外整棵树的最小开销（ $u$ 状态为 $s$ ），按先根序自顶向下递推（ $p$ 为 $u$ 的父亲）：

g_0(u) = g_1(p) + f_1(p) - \operatorname{con}(u, 1), \qquad g_1(u) = \min\Bigl(g_0(p) + f_0(p) - f_1(u),\; g_1(p) + f_1(p) - \operatorname{con}(u, 1)\Bigr).

含义是： $u$ 不驻军时边 $(p,u)$ 只能靠父亲驻军； $u$ 驻军时父亲两种状态都行，取更小者；两种情形都要把 $u$ 子树那份从父亲的账里扣掉，避免重复计算。记 $T_s(u) = f_s(u) + g_s(u)$ ，它就是" $u$ 状态固定为 $s$ 、其余全部自由取优"的全树开销。

路径段的转移可以结合。 关键观察：一段路径在"两端状态固定"时，段内（含各结点的悬挂子树）的最小开销只由两端状态决定，且这样的转移是可结合的。把路径段 $\{u, \dots, \text{top 的前一个点}\}$ 在底端状态 $x$ 、顶端状态 $y$ 下的最小开销记为矩阵元 $M[x][y]$ ，那么"先走下半段、再走上半段"就是一次 min-plus 矩阵乘法：

\bigl(M_{\text{下}} \otimes M_{\text{上}}\bigr)[x][y] = \min_z \Bigl( M_{\text{下}}[x][z] + M_{\text{上}}[z][y] \Bigr),

其中 $z$ 是接缝处结点的状态。朴素做法每次询问沿路径逐点做这个链式 DP，最坏 $O(n)$ ；既然转移可结合，就可以像 LCA 一样倍增预处理： $f[k][u]$ 表示从 $u$ 向上 $2^k$ 层这段路径（含 $u$ 、不含顶端祖先）的 $2 \times 2$ 转移矩阵。

合并时有一个必须处理的细节： $v = \operatorname{anc}[u][2^{k-1}]$ 在上半段里是底端，矩阵里带的是 $f_s(v)$ 整棵子树；但下半段已经算过 $v$ 在路径下方那个孩子 $w$ 的子树，因此要扣掉一份：

f[k][u][x][y] = \min_z \Bigl( f[k-1][u][x][z] + f[k-1][v][z][y] - \operatorname{con}(w, z) \Bigr).

$k=0$ 的初始矩阵就是单个结点： $f[0][u][x][y] = f_x(u) + [x \lor y]$ （ $[\cdot]$ 表示两端同时为 $0$ 时为 $+\infty$ ，即边 $(u, p(u))$ 必须被覆盖）。

回答一次询问。 先把较深的一端抬到同一深度，再让两端同步上跳到 $c$ 的正下方，每跳一步就用 min-plus 乘法累积一行矩阵，共 $O(\log n)$ 步。设两端最终分别停在 $d_a$ 、 $d_b$ （即 $c$ 在两条路径上的儿子；若某一端本身就是 $c$ ，则该端贡献退化为恒等），对 $c$ 的状态 $m \in \{0, 1\}$ 取最小值：

\text{ans} = \min_m \Bigl( A_x[m] + B_y[m] + T_m(c) - \operatorname{con}(d_a, m) - \operatorname{con}(d_b, m) \Bigr),

其中 $A_x$ 、 $B_y$ 是两条路径累积出的矩阵行（已含强制状态）， $T_m(c)$ 覆盖 $c$ 的悬挂子树与 $c$ 以上的整棵树—— $c$ 的账里包含两个路径孩子，而它们的开销已算在路径段里，所以要各扣掉 $\operatorname{con}(d, m)$ 一份。若结果超出可行上界则输出 $-1$ （路径上的边约束会让不可行情形一路保持 $+\infty$ ）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(ll)1000000000000000000LL; const ll BAD=(ll)100000000000000000LL;
int n,m,kmax; vector<ll> pricev,f0,f1,bestv,top0,top1,fmat; vector<int> parentv,depthv,order; vector<vector<int> > anc,downv;
void build_tree(vector<pair<int,int> >&edges){ vector<vector<int> > adj(n); for(int i=0;i<(int)edges.size();i++){adj[edges[i].first].push_back(edges[i].second); adj[edges[i].second].push_back(edges[i].first);} parentv.assign(n,-1); depthv.assign(n,0); parentv[0]=0; vector<int> st; st.push_back(0); while(!st.empty()){int u=st.back();st.pop_back(); order.push_back(u); for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i]; if(parentv[v]==-1){parentv[v]=u; depthv[v]=depthv[u]+1; st.push_back(v);}}}}
void subtree_cost(){f0.assign(n,0); f1.assign(n,0); bestv.assign(n,0); for(int i=n-1;i>=0;i--){int u=order[i]; f1[u]+=pricev[u]; bestv[u]=min(f0[u],f1[u]); if(u){int p=parentv[u]; f0[p]+=f1[u]; f1[p]+=bestv[u];}}}
void upper_cost(){vector<ll> g0(n),g1(n); for(int idx=0;idx<(int)order.size();idx++){int u=order[idx]; if(!u) continue; int p=parentv[u]; ll stay=g1[p]+f1[p]-bestv[u]; g0[u]=stay; ll leave=g0[p]+f0[p]-f1[u]; g1[u]=min(leave,stay);} top0.assign(n,0); top1.assign(n,0); for(int i=0;i<n;i++){top0[i]=f0[i]+g0[i]; top1[i]=f1[i]+g1[i];}}
void jump_tables(){anc.assign(kmax, vector<int>(n)); anc[0]=parentv; for(int k=1;k<kmax;k++) for(int i=0;i<n;i++) anc[k][i]=anc[k-1][anc[k-1][i]]; downv.assign(kmax+1, vector<int>(n)); for(int i=0;i<n;i++) downv[1][i]=i; for(int k=2;k<=kmax;k++) for(int i=0;i<n;i++) downv[k][i]=downv[k-1][anc[k-2][i]];}
void path_matrices(){fmat.assign((ll)kmax*n*4,0); for(int u=0;u<n;u++){ll vals[4]={INF,f0[u],f1[u],f1[u]}; for(int j=0;j<4;j++) fmat[4*u+j]=vals[j];} for(int k=1;k<kmax;k++){ll prev=(ll)(k-1)*n*4, cur=(ll)k*n*4; int threshold=1<<k; for(int u=0;u<n;u++){ if(depthv[u]<threshold) continue; ll pu=prev+4*u; ll a00=fmat[pu],a01=fmat[pu+1],a10=fmat[pu+2],a11=fmat[pu+3]; int v=anc[k-1][u]; ll pv=prev+4*v; ll b00=fmat[pv],b01=fmat[pv+1],b10=fmat[pv+2],b11=fmat[pv+3]; int w=downv[k][u]; ll c0=f1[w], c1=bestv[w]; ll q=cur+4*u; fmat[q]=min(a00+b00-c0,a01+b10-c1); fmat[q+1]=min(a00+b01-c0,a01+b11-c1); fmat[q+2]=min(a10+b00-c0,a11+b10-c1); fmat[q+3]=min(a10+b01-c0,a11+b11-c1); } }}
struct ClimbRes{int u,w; ll s0,s1;};
ClimbRes climb_step(int k,int u,int w,ll s0,ll s1){ll base=4LL*(k*n+u); ll g00=fmat[base],g01=fmat[base+1],g10=fmat[base+2],g11=fmat[base+3]; ll c0=(w!=u?f1[w]:0), c1=(w!=u?bestv[w]:0); ClimbRes r; r.u=anc[k][u]; r.w=downv[k+1][u]; r.s0=min(s0+g00-c0, s1+g10-c1); r.s1=min(s0+g01-c0, s1+g11-c1); return r;}
ll answer_query(int a,int x,int b,int y){int la=a,lb=b,da=a,db=b; ll a0=(x==0?0:INF), a1=(x==0?INF:0), b0=(y==0?0:INF), b1=(y==0?INF:0); if(depthv[la]!=depthv[lb]){for(int k=kmax-1;k>=0;k--){int step=1<<k; if(depthv[la]-step>=depthv[lb]){ClimbRes r=climb_step(k,la,da,a0,a1); la=r.u; da=r.w; a0=r.s0; a1=r.s1;} else if(depthv[lb]-step>=depthv[la]){ClimbRes r=climb_step(k,lb,db,b0,b1); lb=r.u; db=r.w; b0=r.s0; b1=r.s1;}}} if(la!=lb){for(int k=kmax-1;k>=0;k--) if(anc[k][la]!=anc[k][lb]){ClimbRes ra=climb_step(k,la,da,a0,a1); la=ra.u; da=ra.w; a0=ra.s0; a1=ra.s1; ClimbRes rb=climb_step(k,lb,db,b0,b1); lb=rb.u; db=rb.w; b0=rb.s0; b1=rb.s1;}}
    int c,wa,wb; ll va0,va1,vb0,vb1; if(la==lb){c=la; va0=a0; va1=a1; vb0=b0; vb1=b1; wa=(a!=c?da:-1); wb=(b!=c?db:-1);} else {c=parentv[la]; ll sa0=a0+f0[la]-(la!=a?f1[da]:0); ll sa1=a1+f1[la]-(la!=a?bestv[da]:0); va0=sa1; va1=min(sa0,sa1); ll sb0=b0+f0[lb]-(lb!=b?f1[db]:0); ll sb1=b1+f1[lb]-(lb!=b?bestv[db]:0); vb0=sb1; vb1=min(sb0,sb1); wa=la; wb=lb;} ll cut0=(wa>=0?f1[wa]:0)+(wb>=0?f1[wb]:0); ll cut1=(wa>=0?bestv[wa]:0)+(wb>=0?bestv[wb]:0); ll cost0=va0+vb0+top0[c]-cut0; ll cost1=va1+vb1+top1[c]-cut1; ll least=min(cost0,cost1); return least>=BAD?-1:least;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); string type; if(!(cin>>n>>m>>type)) return 0; pricev.resize(n); for(int i=0;i<n;i++) cin>>pricev[i]; vector<pair<int,int> > edges(n-1); for(int i=0;i<n-1;i++){cin>>edges[i].first>>edges[i].second; edges[i].first--; edges[i].second--;} build_tree(edges); subtree_cost(); upper_cost(); kmax=1; int md=0; for(int i=0;i<n;i++) md=max(md,depthv[i]); while((1<<kmax)<=md) kmax++; jump_tables(); path_matrices(); for(int i=0;i<m;i++){int a,x,b,y;cin>>a>>x>>b>>y; cout<<answer_query(a-1,x,b-1,y); if(i+1<m) cout<<'\n';} return 0;}

python

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
196
197
198
199
200
201
202
203
204
205#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 14:16
# update_at: 2026-10-02 14:16

import sys
from array import array

INF = 10**18  # 不可行的代价哨兵
BAD = 10**17  # 真实开销上界约 1e10，累计值超过它即判定不可行


def build_tree(n: int, edges: list[tuple[int, int]]) -> tuple[array, array, list[int]]:
    """以 0 号点为根展开无根树，返回每个点的父亲、深度和先根序。"""
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    parent = array("i", [-1] * n)
    parent[0] = 0  # 根的父亲指向自己，倍增表越界时自然收敛到根
    depth = array("i", bytes(4 * n))
    order: list[int] = []
    stack = [0]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if parent[v] == -1:
                parent[v] = u
                depth[v] = depth[u] + 1
                stack.append(v)
    return parent, depth, order


def subtree_cost(price: list[int], parent: array, order: list[int]) -> tuple[array, array, array]:
    """自底向上做树形 DP：f0/f1[u] 是 u 不驻军/驻军时子树的最小开销，best 取两者较小。"""
    n = len(price)
    f0 = array("q", bytes(8 * n))
    f1 = array("q", bytes(8 * n))
    best = array("q", bytes(8 * n))
    for i in range(n - 1, -1, -1):  # 先根序倒过来 = 子树先于父亲处理
        u = order[i]
        f1[u] += price[u]  # 驻军要付自己的花费
        best[u] = f0[u] if f0[u] < f1[u] else f1[u]
        if u:  # 把 u 的贡献推给父亲：父亲不驻军则 u 必须驻军，否则 u 自由取小
            p = parent[u]
            f0[p] += f1[u]
            f1[p] += best[u]
    return f0, f1, best


def upper_cost(parent: array, order: list[int], f0: array, f1: array, best: array) -> tuple[array, array]:
    """自顶向下换根：top0/top1[u] = 除 u 的子树外整棵树的最小开销（u 状态 0/1）。"""
    n = len(parent)
    g0 = array("q", bytes(8 * n))
    g1 = array("q", bytes(8 * n))
    for u in order:
        if not u:
            continue
        p = parent[u]
        stay = g1[p] + f1[p] - best[u]  # 父亲驻军：扣掉 u 子树那份，边由父亲覆盖
        g0[u] = stay  # u 不驻军时边 (p,u) 只能靠父亲，故只保留 stay
        leave = g0[p] + f0[p] - f1[u]  # 父亲不驻军：u 必须驻军，边由 u 覆盖
        g1[u] = leave if leave < stay else stay
    top0 = array("q", (f0[i] + g0[i] for i in range(n)))
    top1 = array("q", (f1[i] + g1[i] for i in range(n)))
    return top0, top1


def jump_tables(parent: array, kmax: int) -> tuple[list, list]:
    """倍增祖先表 anc[k][u]；down[k][u] = u 上方第 2^(k-1)-1 级祖先，供跳步取修正项。"""
    n = len(parent)
    anc = [parent]
    for k in range(1, kmax):
        prev = anc[k - 1]
        anc.append(array("i", (prev[prev[i]] for i in range(n))))
    down: list = [None, array("i", range(n))]  # down[1][u] = u 自身（跳 1 层时正下方就是它）
    for k in range(2, kmax + 1):
        low, up = down[k - 1], anc[k - 2]
        down.append(array("i", (low[up[i]] for i in range(n))))
    return anc, down


def path_matrices(n: int, kmax: int, depth: array, anc: list, down: list,
                  f0: array, f1: array, best: array) -> array:
    """预处理路径倍增矩阵：fmat 压平成 kmax*n*4，每块是 2x2 的 min-plus 矩阵。

    矩阵 (x, y) = 路径 {u, ..., 2^k 祖先的前一个点} 在两端状态 x、y 下的最小开销，
    含路径点的花费与悬挂子树，不含顶端祖先本身。
    """
    fmat = array("q", bytes(32 * n * kmax))  # kmax 层，先全部置 0
    fmat[:4 * n] = array("q", (v for u in range(n) for v in (INF, f0[u], f1[u], f1[u])))  # 0 层
    for k in range(1, kmax):
        prev, cur = (k - 1) * n * 4, k * n * 4
        threshold = 1 << k
        ak, dk = anc[k - 1], down[k]
        for u in range(n):
            if depth[u] < threshold:
                continue  # 深度不够的点没有 2^k 祖先，该块永远读不到
            pu = prev + 4 * u
            a00, a01, a10, a11 = fmat[pu], fmat[pu + 1], fmat[pu + 2], fmat[pu + 3]
            v = ak[u]
            pv = prev + 4 * v
            b00, b01, b10, b11 = fmat[pv], fmat[pv + 1], fmat[pv + 2], fmat[pv + 3]
            w = dk[u]  # 合并处 v 在路径上的孩子：两半都算过它，要扣掉一份
            c0, c1 = f1[w], best[w]
            q = cur + 4 * u
            t, r = a00 + b00 - c0, a01 + b10 - c1
            fmat[q] = t if t < r else r
            t, r = a00 + b01 - c0, a01 + b11 - c1
            fmat[q + 1] = t if t < r else r
            t, r = a10 + b00 - c0, a11 + b10 - c1
            fmat[q + 2] = t if t < r else r
            t, r = a10 + b01 - c0, a11 + b11 - c1
            fmat[q + 3] = t if t < r else r
    return fmat


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    n = int(next(tokens))
    m = int(next(tokens))
    _ = next(tokens)  # 官方子任务类型标记，如 "C3"；只决定官方部分分，本解法对任意形态通用
    data = iter(map(int, tokens))
    price = [next(data) for _ in range(n)]
    edges = [(next(data) - 1, next(data) - 1) for _ in range(n - 1)]

    parent, depth, order = build_tree(n, edges)
    f0, f1, best = subtree_cost(price, parent, order)
    top0, top1 = upper_cost(parent, order, f0, f1, best)
    kmax = max(1, max(depth).bit_length())  # 最深点需要的倍增层数
    anc, down = jump_tables(parent, kmax)
    fmat = path_matrices(n, kmax, depth, anc, down, f0, f1, best)

    def climb(k: int, u: int, w: int, s0: int, s1: int) -> tuple[int, int, int, int]:
        """u 上跳 2^k 层：w 是跳之前 u 正下方的路径点（首跳时 w == u）。

        返回新位置、新位置正下方的点、累乘后的矩阵行 (s0, s1)。
        """
        base = 4 * (k * n + u)
        g00, g01, g10, g11 = fmat[base], fmat[base + 1], fmat[base + 2], fmat[base + 3]
        # f 矩阵把 u 整棵子树都记在 u 头上，而 u 下方那段已算进累积行；
        # 只在之前累积过（w != u）时扣掉路径孩子那份，避免重复计算
        c0 = f1[w] if w != u else 0
        c1 = best[w] if w != u else 0
        return (anc[k][u], down[k + 1][u],
                min(s0 + g00 - c0, s1 + g10 - c1), min(s0 + g01 - c0, s1 + g11 - c1))

    def answer(a: int, x: int, b: int, y: int) -> int:
        """强制 a 取状态 x、b 取状态 y 时的最小开销；不可行返回 -1。"""
        la, lb = a, b
        da, db = a, b  # 两端当前位置正下方的路径点，LCA 就是某一端时用它修正
        a0 = 0 if x == 0 else INF  # 单位矩阵的第 x 行：只有状态 x 代价为 0
        a1 = INF if x == 0 else 0
        b0 = 0 if y == 0 else INF
        b1 = INF if y == 0 else 0

        # 第一阶段：把较深的一端逐级抬到同一深度，顺路累乘路径转移矩阵
        if depth[la] != depth[lb]:
            for k in range(kmax - 1, -1, -1):
                step = 1 << k
                if depth[la] - step >= depth[lb]:
                    la, da, a0, a1 = climb(k, la, da, a0, a1)
                elif depth[lb] - step >= depth[la]:
                    lb, db, b0, b1 = climb(k, lb, db, b0, b1)

        # 第二阶段：两端同步上跳到 LCA 正下方（两端的 2^k 祖先不同时才跳）
        if la != lb:
            for k in range(kmax - 1, -1, -1):
                if anc[k][la] != anc[k][lb]:
                    la, da, a0, a1 = climb(k, la, da, a0, a1)
                    lb, db, b0, b1 = climb(k, lb, db, b0, b1)

        if la == lb:
            c = la  # LCA 恰好是被抬上来的那一端
            va0, va1, vb0, vb1 = a0, a1, b0, b1
            wa = da if a != c else -1  # c 的路径孩子（被抬那端正下方），算 c 时要扣掉
            wb = db if b != c else -1
        else:
            c = parent[la]  # 两端分别停在 LCA 的两个儿子上，还差最后一步到 c
            # 两端自己的花费还没算：F 减去朝向路径下方那份悬挂贡献，再补上边约束
            sa0 = a0 + f0[la] - (f1[da] if la != a else 0)
            sa1 = a1 + f1[la] - (best[da] if la != a else 0)
            va0, va1 = sa1, sa0 if sa0 < sa1 else sa1
            sb0 = b0 + f0[lb] - (f1[db] if lb != b else 0)
            sb1 = b1 + f1[lb] - (best[db] if lb != b else 0)
            vb0, vb1 = sb1, sb0 if sb0 < sb1 else sb1
            wa, wb = la, lb

        # c 自身的花费与悬挂子树（扣除两个路径孩子）再加上 c 以上的整棵树
        cut0 = (f1[wa] if wa >= 0 else 0) + (f1[wb] if wb >= 0 else 0)
        cut1 = (best[wa] if wa >= 0 else 0) + (best[wb] if wb >= 0 else 0)
        cost0 = va0 + vb0 + top0[c] - cut0
        cost1 = va1 + vb1 + top1[c] - cut1
        least = cost0 if cost0 < cost1 else cost1
        return -1 if least >= BAD else least

    queries = [(next(data) - 1, next(data), next(data) - 1, next(data)) for _ in range(m)]
    sys.stdout.write("\n".join(str(answer(*q)) for q in queries))


if __name__ == "__main__":
    solve()

复杂度

预处理：子树 DP 与换根 DP 各 $O(n)$ ，倍增表与路径矩阵 $O(n \log n)$ 。
每次询问：两次抬升共 $O(\log n)$ 跳，每跳 $O(1)$ 的 $2 \times 2$ 矩阵乘法，故 $O(\log n)$ 。
总复杂度 $O((n + m) \log n)$ ，与 $n, m \leqslant 10^5$ 同阶；倍增表与矩阵占 $O(n \log n)$ 空间。

总结

本题的模型是树上的带权顶点覆盖：两状态树形 DP 一次 $O(n)$ 求出无约束最优。询问引入两个结点的强制状态后，约束只沿两条到 LCA 的路径传播，LCA 以上的部分用换根 DP 压成只与 LCA 状态有关的 $T_s(c)$ 。路径段"两端状态固定"的最优化对应可结合的 $2 \times 2$ min-plus 转移，于是用倍增把朴素的逐点链式 DP 提升为每次询问 $O(\log n)$ ；合并两半时记得把接缝结点在路径下方的悬挂子树扣掉一份，这是本题最容易出错的地方。

图示解析

样例的树形（边权无，括号内为驻军花费）：

graph TD
    1(("1<br/>p=2")) --- 5(("5<br/>p=9"))
    5 --- 2(("2<br/>p=4"))
    5 --- 3(("3<br/>p=1"))
    3 --- 4(("4<br/>p=3"))

三个询问的约束与结果（询问互相独立）：

询问	约束	最优驻军方案	开销
1	1 不驻军、3 不驻军	4、5 驻军	12
2	2 驻军、3 驻军	1、2、3 驻军	7
3	1 不驻军、5 不驻军	边 $(1,5)$ 两端都不驻军	-1

询问 1 中， $c = 1$ 恰是被强制的一端： $a$ 端退化为恒等行，路径段只有 $b$ 端的 $3 \to 1$ （结点 $3, 5$ ），累积矩阵行 $B[0][m] = 12$ ； $c$ 的账 $T_0(1) = 10$ 已含结点 5 子树，扣掉 $\operatorname{con}(5, 0) = f_1(5) = 10$ 后得到 $12 + 10 - 10 = 12$ 。

询问 2 中 $c = 5$ ，两端各自只有一段矩阵（ $\{2\}$ 与 $\{3\}$ ），最后对 $m$ 取小： $m = 0$ 时 $4 + 1 + T_0(5) - f_1(2) - f_1(3) = 5 + 7 - 4 - 1 = 7$ ； $m = 1$ 时为 $4 + 1 + T_1(5) - \operatorname{con}(2,1) - \operatorname{con}(3,1) = 5 + 10 - 0 - 1 = 14$ ，故答案 $7$ 。

询问 3 中 $c = 1$ 、 $b = 5$ 的状态为 $0$ ： $b$ 端矩阵行 $B[0][m] = f_0(5) + [0 \lor m]$ 只有 $m = 1$ 才有限（ $5$ 不驻军则边 $(1,5)$ 只能靠 $1$ 覆盖），但 $a = c = 1$ 又强制 $m = 0$ ，两边矛盾，累加值保持 $+\infty$ ，输出 $-1$ 。

题目描述

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

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

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

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

输入输出格式

输入格式：

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

第 $2$ 行 $n$ 个整数 $p\_i$ ，表示编号 $i$ 的城市中驻扎军队的花费。

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

接下来 $m$ 行，第 $j$ 行四个整数 $a,x,b,y(a ≠ b)$ ，表示第 $j$ 个要求是在城市 $a$ 驻扎 $x$ 支军队，在城市 $b$ 驻扎 $y$ 支军队。其中， $x$ 、 $y$ 的取值只有 $0$ 或 $1$ ：若 $x$ 为 $0$ ，表示城市 $a$ 不得驻扎军队，若 $x$ 为 $1$ ，表示城市 $a$ 必须驻扎军队；若 $y $为 $0$ ，表示城市 $b$ 不得驻扎军队，若 $y $为 $1$ ，表示城市 $b$ 必须驻扎军队。

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

输出格式：

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

输入输出样例

输入样例#1： 复制

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： 复制

12 7 -1

说明

【样例解释】

对于第一个要求，在 $4$ 号和 $5$ 号城市驻扎军队时开销最小。

对于第二个要求，在 $1$ 号、 $2$ 号、 $3$ 号城市驻扎军队时开销最小。

第三个要求是无法满足的，因为在 $1$ 号、 $5$ 号城市都不驻扎军队就意味着由道路直接连接的两座城市中都没有驻扎军队。

【数据规模与约定】

对于 $100\\%$ 的数据， $n,m ≤ 100000,1 ≤ p\_i ≤ 100000$ 。

数据类型的含义：

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