【题解】P14468 [COCI 2025/2026 #1] 和谐 / Harmonija（线段树 DDP 版本）

前置：P4719 【模板】动态 DP - 洛谷

用线段树 DDP 喵，因为我刚刚学的不用白学了。结果发现这道题能用倍增矩乘气四我了。

我的线段树 DDP 博客：【题解】P4719 【模板】动态 DP（线段树版本）-CSDN博客

https://www.luogu.com.cn/problem/P14468

0.抽象化题意

1.确定算法和矩阵计算

我们发现动态规划每次转移来源是固定的，所以可以使用矩阵乘法加速。

而树上矩乘查询是标准的动态 DP，考虑使用此算法。

还是阉割版的，因为题目没要求修改。

2.算法流程

在计算时，矩阵乘法的顺序至关重要，因为矩阵乘法不满足交换律。

从祖先到后代：线段树从左到右恰好是深度递增的顺序，矩阵直接按原顺序乘即可。

如从后代到祖先：线段树从左到右是深度递增，但我们需要的是深度递减的顺序。

所以线段树的每个节点不仅要维护“从左到右”的乘积，还要维护“从右到左”的乘积。

当查询（向上爬）时，我们取到的区间顺序是反的，需要用维护好的逆序乘积。

最终合并左右两段路径时，必须保证：靠近的先乘，靠近的后乘。

举个例子，查询路径：

收集到这段的矩阵（顺序为从向上到，即深度递减），用逆序乘积合并。

收集到这段的矩阵（顺序为从向下到，即深度递增），用正序乘积合并。

最终的总转移矩阵 =矩阵部分矩阵部分。

用乘上这个总矩阵，取最大值。

3.代码

#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; const int inf = 1e16; // 输入数据：c[i] 红权值，p[i] 蓝权值 int n, q, c[N], p[N]; int f[N][25]; int dep[N], fa[N]; int dfn[N], siz[N], top[N], son[N], id[N], tsp; vector<int> G[N]; #define lc(p) (p << 1) #define rc(p) ((p << 1) | 1) void dfsa(int u) { siz[u] = 1; dep[u] = dep[fa[u]] + 1; for (int v : G[u]) { if (v != fa[u]) { f[v][0] = fa[v] = u; dfsa(v); siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v; } } } void dfsb(int u, int tp) { top[u] = tp; dfn[u] = ++tsp; id[dfn[u]] = u; if (!son[u]) return; dfsb(son[u], tp); for (int v : G[u]) { if (v != fa[u] && v != son[u]) dfsb(v, v); } } // 求 u 向上走 k 步的祖先 int getkth(int u, int k) { for (int i = 20; i >= 0; --i) if (k & (1 << i)) u = f[u][i]; return u; } // 若 v 在 u 的子树内，返回 u 的儿子中指向 v 的那个（即路径上下一个节点） // 否则返回 fa[u]（路径需要向上走） int getse(int u, int v) { if (dfn[v] >= dfn[u] && dfn[v] < dfn[u] + siz[u]) return getkth(v, dep[v] - dep[u] - 1); return fa[u]; } /* 状态编号对应差值 d = 红点数 - 蓝点数： 0: d=0 1: d=1 2: d=2 3: d=-1 4: d=-2 合法范围 [-2, 2] */ struct Matrix { int a[5][5]; Matrix() { for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) a[i][j] = -inf; } // max-plus 矩阵乘法 Matrix operator*(const Matrix &b) const { Matrix c; for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) for (int k = 0; k < 5; ++k) c.a[i][j] = max(c.a[i][j], a[i][k] + b.a[k][j]); return c; } }; // 线段树：T1 维护正序（左->右），T2 维护逆序（右->左） Matrix T1[4 * N], T2[4 * N]; // 建树：叶子节点为单个点的转移矩阵 void build(int x, int L, int R) { if (L == R) { int u = id[L]; // 根据状态编号填入转移值 // 蓝转移：d -> d-1 T1[x].a[1][0] = p[u]; // d=1 -> d=0 T1[x].a[2][1] = p[u]; // d=2 -> d=1 T1[x].a[0][3] = p[u]; // d=0 -> d=-1 T1[x].a[3][4] = p[u]; // d=-1 -> d=-2 // 红转移：d -> d+1 T1[x].a[3][0] = c[u]; // d=-1 -> d=0 T1[x].a[0][1] = c[u]; // d=0 -> d=1 T1[x].a[1][2] = c[u]; // d=1 -> d=2 T1[x].a[4][3] = c[u]; // d=-2 -> d=-1 T2[x] = T1[x]; return; } int MID = (L + R) >> 1; build(lc(x), L, MID); build(rc(x), MID + 1, R); // T1：左子树 × 右子树（深度递增顺序） T1[x] = T1[lc(x)] * T1[rc(x)]; // T2：右子树 × 左子树（深度递减顺序） T2[x] = T2[rc(x)] * T2[lc(x)]; } // 查询区间 [l, r] 的正序乘积（深度递增） Matrix query1(int x, int L, int R, int l, int r) { if (l <= L && R <= r) return T1[x]; int MID = (L + R) >> 1; if (r <= MID) return query1(lc(x), L, MID, l, r); if (l > MID) return query1(rc(x), MID + 1, R, l, r); return query1(lc(x), L, MID, l, r) * query1(rc(x), MID + 1, R, l, r); } // 查询区间 [l, r] 的逆序乘积（深度递减） Matrix query2(int x, int L, int R, int l, int r) { if (l <= L && R <= r) return T2[x]; int MID = (L + R) >> 1; if (r <= MID) return query2(lc(x), L, MID, l, r); if (l > MID) return query2(rc(x), MID + 1, R, l, r); return query2(rc(x), MID + 1, R, l, r) * query2(lc(x), L, MID, l, r); } // 查询路径 u -> v 的转移矩阵（u 和 v 是原始点，路径按从 u 到 v 的顺序） Matrix qry(int u, int v) { Matrix a, b; // a 用于左侧（深度递减部分），b 用于右侧（深度递增部分） for (int i = 0; i < 5; ++i) a.a[i][i] = b.a[i][i] = 0; // 初始化为单位矩阵 while (top[u] != top[v]) { if (dep[top[u]] > dep[top[v]]) { // u 所在重链更深，从 u 向上到 top[u] 是逆序（深度递减） a = a * query2(1, 1, n, dfn[top[u]], dfn[u]); u = fa[top[u]]; } else { // v 所在重链更深，从 top[v] 向下到 v 是正序（深度递增） b = query1(1, 1, n, dfn[top[v]], dfn[v]) * b; v = fa[top[v]]; } } // 现在在同一条重链上 if (dep[u] > dep[v]) { // u 更深，从 u 向上到 v 是逆序 a = a * query2(1, 1, n, dfn[v], dfn[u]); } else { // v 更深（或相等），从 u 向下到 v 是正序 b = query1(1, 1, n, dfn[u], dfn[v]) * b; } // 最终总转移矩阵 = a * b return a * b; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> c[i]; for (int i = 1; i <= n; ++i) cin >> p[i]; for (int i = 1, u, v; i < n; ++i) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfsa(1); dfsb(1, 1); // 倍增预处理 for (int i = 1; i <= 20; ++i) for (int j = 1; j <= n; ++j) f[j][i] = f[f[j][i - 1]][i - 1]; build(1, 1, n); while (q--) { int u, v; cin >> u >> v; // ans 作为行向量：初始差值 d = 0（状态0） // 但为了方便，我们直接构造处理完第一个点 u 之后的行向量 // 即从状态 0 出发，选择红色或蓝色后的结果 Matrix ans; ans.a[0][1] = c[u]; // 染红 → 差值+1 → 状态1 ans.a[0][3] = p[u]; // 染蓝 → 差值-1 → 状态3 if (u != v) { // 获取路径上下一个点（即 u 的孩子或父亲） int nxt = getse(u, v); // 将剩余路径的转移矩阵乘上 ans = ans * qry(nxt, v); } // 最终答案：取行向量中五个状态的最大值 int res = max({ans.a[0][0], ans.a[0][1], ans.a[0][2], ans.a[0][3], ans.a[0][4]}); cout << res << '\n'; } return 0; }