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

前置P4719 【模板】动态 DP - 洛谷用线段树 DDP 喵因为我刚刚学的不用白学了。结果发现这道题能用倍增矩乘气四我了。我的线段树 DDP 博客【题解】P4719 【模板】动态 DP线段树版本-CSDN博客https://www.luogu.com.cn/problem/P144680.抽象化题意1.确定算法和矩阵计算我们发现动态规划每次转移来源是固定的所以可以使用矩阵乘法加速。而树上矩乘查询是标准的动态 DP考虑使用此算法。还是阉割版的因为题目没要求修改。2.算法流程在计算时矩阵乘法的顺序至关重要因为矩阵乘法不满足交换律。从祖先到后代线段树从左到右恰好是深度递增的顺序矩阵直接按原顺序乘即可。如从后代到祖先线段树从左到右是深度递增但我们需要的是深度递减的顺序。所以线段树的每个节点不仅要维护“从左到右”的乘积还要维护“从右到左”的乘积。当查询向上爬时我们取到的区间顺序是反的需要用维护好的逆序乘积。最终合并左右两段路径时必须保证靠近的先乘靠近的后乘。举个例子查询路径收集到这段的矩阵顺序为从向上到即深度递减用逆序乘积合并。收集到这段的矩阵顺序为从向下到即深度递增用正序乘积合并。最终的总转移矩阵 矩阵部分矩阵部分。用乘上这个总矩阵取最大值。3.代码#includebits/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; vectorint 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: d0 1: d1 2: d2 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]; // d1 - d0 T1[x].a[2][1] p[u]; // d2 - d1 T1[x].a[0][3] p[u]; // d0 - d-1 T1[x].a[3][4] p[u]; // d-1 - d-2 // 红转移d - d1 T1[x].a[3][0] c[u]; // d-1 - d0 T1[x].a[0][1] c[u]; // d0 - d1 T1[x].a[1][2] c[u]; // d1 - d2 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; }