E - Echoes of 24 - 题解

标签与难度

标签: 树链剖分, 线段树, 动态规划, 位运算, 树上路径查询, 算法优化难度: 2500

题目大意喵~

你好呀，指挥官！咱是我，对解题超有热情的说！这道题是关于可爱的立华奏酱的故事呢，喵~

故事发生在一棵有 $N$ 个节点的树上，每个节点都有一个值 $a_i$ 。我们需要处理 $Q$ 次操作，操作有两种：

查询 1 l r: 询问从节点 $l$ 到节点 $r$ 的简单路径，能否通过一系列操作让最终结果变成 24？操作规则是这样的：设路径上的值为 $w_1, w_2, \dots, w_k$ 。我们从一个等于 $w_1$ 的计数器开始。对于路径上接下来的每个值 $w_i$ （从 $i=2$ 到 $k$ ），我们可以选择将它与计数器相加，或者相乘。
更新 2 x d: 将节点 $x$ 的值修改为 $d$ 。

我们需要对每个查询快速给出答案，是 "1" (可以) 还是 "0" (不可以)，喵~

解题思路分析

这道题看起来好复杂呀，又是树上路径，又是动态计算，还有修改操作，真是对脑瓜子的一大考验呢，喵~ 但是别怕，跟着我的思路，一步一步把它解剖开来！

核心问题：如何得到 24？

首先，我们来思考最核心的部分：给定一个数列 $w_1, w_2, \dots, w_k$ ，如何判断它能否凑出 24？

这是一个典型的动态规划问题！我们可以定义 dp[i] 为处理完前 $i$ 个数后，所有可能得到的数值集合。

dp[1] = {w_1}
dp[i] = { val + w_i | val ∈ dp[i-1] } ∪ { val * w_i | val ∈ dp[i-1] }

但是，这个集合的大小可能会指数级增长，我们可不能让内存和时间爆炸呀！

注意到目标值是 24，一个非常小的数字！这给了我们一个巨大的提示。如果计算过程中的某个中间值变得比 24 大，比如变成了 30，那么再对它进行加法（+w_i）或者乘法（*w_i，因为 $w_i \ge 1$ ）之后，结果只会越来越大，就再也回不到 24 了。

所以，我们只需要关心那些不大于 24 的可能结果！

这启发我们用一个大小为 25 的bool数组或者一个位掩码 (bitmask) 来作为 DP 的状态。mask 的第 j 位为 1，当且仅当数值 j 是可以被凑出来的。

DP 状态: mask，一个 32 位整数，(mask >> j) & 1 表示是否能得到 j。
初始状态: mask = 1 << w_1 (当然，如果 w_1 > 24，就无法开始了)。

转移: 对于路径上的下一个数 w 和当前的 old_mask，新的 new_mask 计算如下：

new_mask = 0
for j from 0 to 24:
  if (old_mask >> j) & 1:  // 如果 j 是可达的
    if j + w <= 24: new_mask |= (1 << (j + w))
    if j * w <= 24: new_mask |= (1 << (j * w))

这样，对于一条路径，我们就可以在 $O(路径长度 \times 25)$ 的时间内解决问题。但是路径可能很长，每次查询都这么做还是会超时。

关键观察：1 的特殊性与稀疏的“有效数字”

路径上的数值 $a_i$ 对结果的影响很大。

如果 $a_i = 1$ ，加法 +1 使结果加一，乘法 *1 结果不变。1 像一个“调节器”。
如果 $a_i > 1$ ，加法和乘法都会让结果变大（除非原值为0或1）。我们叫它们“重数字”吧。

让我们想想，如果一条路径上“重数字”太多会发生什么？比如路径上有 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2（12个2），还有一个起始值 2。如果我们全用加法，总和是 $2 \times 13 = 26$ ，已经大于 24 了。任何乘法只会让结果更大。所以，如果一条路径上“重数字”太多，它们的和很容易就超过 24，导致无法凑出 24。具体来说，如果路径上所有“重数字”的和大于 24，那么无论如何操作，最终结果都将大于 24。因为每个“重数字”至少是 2，所以如果路径上“重数字”的个数超过 12 个，它们的和就至少是 $2 \times 13 = 26$ （算上起点）或者 $2 \times 12 = 24$ 。所以我们得到一个重要的剪枝： 如果一条路径上值大于 1 的节点超过了一个很小的数目（比如 12 个），那么几乎不可能凑出 24。我们可以直接判定为 0。

这就把问题分成了两种情况：

“重”路径: 路径上“重数字”节点超过 12 个。直接输出 0。
“稀疏”路径: 路径上“重数字”节点很少（ $\le 12$ 个）。

对于“稀疏”路径，我们只需要关心这些少数的“重数字”节点，以及它们之间被多少个值为 1 的节点隔开。

终极武器：树链剖分 + 线段树

要在树上高效处理带修改的路径查询，树链剖分 (HLD) + 线段树就是我们的不二之选，喵！

树链剖分: 将树拆成若干条重链，把树上路径问题转化为序列上的区间问题。
线段树: 维护剖分后序列的信息。

我们需要线段树做什么呢？

快速统计路径上“重数字”的个数：这是为了我们的剪枝。线段树的每个节点维护其代表的区间内“重数字”的个数。
快速找出所有“重数字”节点: 如果个数不多，我们就需要把它们都抓出来！线段树节点可以只存个数，查询时如果一个区间的个数不为0，就递归下去找。因为总数很少，所以找起来很快。

整合起来的完整算法

预处理:
- 对树进行树链剖分，得到每个节点的 dfn（DFS序）、top（所在重链顶端）等信息。
- 建立一棵线段树，维护 dfn 序。线段树节点 [l, r] 存储区间 [l, r] 中“重数字”的个数。
- 为了优化DP，我们可以预处理出转移函数。apply_op(mask, w) 和 apply_ones(mask, k)，分别代表对当前状态mask作用一个重数字w和作用k个1（即k次加1）。
处理修改 2 x d:
- 更新 a[x] 的值。
- 判断 a[x] 的旧值和新值是否跨越了 1 和 >1 的界限。
- 如果是，比如从 1 变成 2，或者从 5 变成 1，就在线段树上对 dfn[x] 位置进行单点修改（个数+1或-1）。
处理查询 1 l r: a. 统计“重数字”个数: 利用树链剖分将 l-r 路径拆成 $O(\log N)$ 个 dfn 序上的区间，在线段树上查询这些区间的“重数字”个数总和。 b. 剪枝: 如果总个数 count_heavy > 12，直接输出 0。 c. 特殊情况: 如果 count_heavy == 0，说明路径上全是 1。结果就是路径长度 dist(l, r) + 1。判断它是否等于 24 即可。 d. 稀疏路径DP: i. 提取节点: 再次遍历 l-r 路径上的 $O(\log N)$ 个区间，在线段树上找出所有“重数字”节点的 dfn，从而得到节点编号。 ii. 构建计算序列: 我们得到了一个有序的“重数字”节点列表。路径就是 l -> ... -> v_1 -> ... -> v_2 -> ... -> r。计算出它们之间的距离，即中间有多少个 1。 iii. 执行DP: - 初始 mask = 1 << min(a[l], 25)。 - 沿着路径，交替应用 apply_op 和 apply_ones 来更新 mask。 - 例如，从当前节点 curr 到下一个重节点 next_heavy，中间有 k = dist(curr, next_heavy) - 1 个 1。先用 apply_ones(mask, k)，再用 apply_op(mask, a[next_heavy])。 iv. 检查结果: 最后检查 (final_mask >> 24) & 1 是否为 1。

这样，一个复杂的问题就被我们分解成几个熟悉的模块，然后巧妙地组合起来解决啦！是不是感觉清晰多了？喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，加了很多注释，希望能帮助你理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const int MAXN = 500005;
const int HEAVY_THRESHOLD = 13; // 经验阈值, 超过这个数的重节点路径很难凑出24
const int TARGET = 24;

// --- 图和树链剖分 ---
vector<int> adj[MAXN];
int a[MAXN];
int n, q;

int parent[MAXN], depth[MAXN], sz[MAXN], heavy_son[MAXN];
int top[MAXN], dfn[MAXN], rev_dfn[MAXN], timer;

void dfs1(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    sz[u] = 1;
    heavy_son[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > max_sz) {
            max_sz = sz[v];
            heavy_son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++timer;
    rev_dfn[timer] = u;
    if (heavy_son[u] != -1) {
        dfs2(heavy_son[u], t);
    }
    for (int v : adj[u]) {
        if (v == parent[u] || v == heavy_son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (depth[top[u]] > depth[top[v]]) {
            u = parent[top[u]];
        } else {
            v = parent[top[v]];
        }
    }
    return depth[u] < depth[v] ? u : v;
}

int dist(int u, int v) {
    int ancestor = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[ancestor];
}

// --- 线段树 ---
int heavy_count_seg[MAXN * 4];

void push_up(int node) {
    heavy_count_seg[node] = heavy_count_seg[node * 2] + heavy_count_seg[node * 2 + 1];
}

void build_seg(int node, int start, int end) {
    if (start == end) {
        heavy_count_seg[node] = (a[rev_dfn[start]] > 1);
        return;
    }
    int mid = (start + end) / 2;
    build_seg(node * 2, start, mid);
    build_seg(node * 2 + 1, mid + 1, end);
    push_up(node);
}

void update_seg(int node, int start, int end, int idx, int val) {
    if (start == end) {
        heavy_count_seg[node] += val;
        return;
    }
    int mid = (start + end) / 2;
    if (start <= idx && idx <= mid) {
        update_seg(node * 2, start, mid, idx, val);
    } else {
        update_seg(node * 2 + 1, mid + 1, end, idx, val);
    }
    push_up(node);
}

int query_seg_count(int node, int start, int end, int l, int r) {
    if (r < start || end < l || l > r) {
        return 0;
    }
    if (l <= start && end <= r) {
        return heavy_count_seg[node];
    }
    int mid = (start + end) / 2;
    return query_seg_count(node * 2, start, mid, l, r) + query_seg_count(node * 2 + 1, mid + 1, end, l, r);
}

void find_heavy_nodes_in_range(int node, int start, int end, int l, int r, vector<int>& result) {
    if (r < start || end < l || l > r || heavy_count_seg[node] == 0) {
        return;
    }
    if (start == end) {
        result.push_back(rev_dfn[start]);
        return;
    }
    int mid = (start + end) / 2;
    find_heavy_nodes_in_range(node * 2, start, mid, l, r, result);
    find_heavy_nodes_in_range(node * 2 + 1, mid + 1, end, l, r, result);
}

// --- 路径查询辅助函数 ---
int query_path_count(int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        res += query_seg_count(1, 1, n, dfn[top[u]], dfn[u]);
        u = parent[top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res += query_seg_count(1, 1, n, dfn[u], dfn[v]);
    return res;
}

void get_path_heavy_nodes(int u, int v, vector<int>& result) {
    vector<int> path_u, path_v;
    while (top[u] != top[v]) {
        if (depth[top[u]] > depth[top[v]]) {
            find_heavy_nodes_in_range(1, 1, n, dfn[top[u]], dfn[u], path_u);
            u = parent[top[u]];
        } else {
            find_heavy_nodes_in_range(1, 1, n, dfn[top[v]], dfn[v], path_v);
            v = parent[top[v]];
        }
    }
    if (depth[u] > depth[v]) swap(u, v);
    find_heavy_nodes_in_range(1, 1, n, dfn[u], dfn[v], path_u);
    
    sort(path_u.begin(), path_u.end(), [&](int n1, int n2){
        return depth[n1] > depth[n2];
    });
    sort(path_v.begin(), path_v.end(), [&](int n1, int n2){
        return depth[n1] < depth[n2];
    });

    for(int node : path_u) result.push_back(node);
    for(int node : path_v) {
        // 避免LCA被重复添加
        if(result.empty() || result.back() != node) {
            result.push_back(node);
        }
    }
}


// --- DP 计算 ---
// 对一个 mask 作用 k 个 1
unsigned int apply_ones(unsigned int mask, int k) {
    while (k-- > 0 && mask != 0) {
        mask |= (mask << 1);
    }
    return mask & ((1 << (TARGET + 1)) - 1);
}

// 对一个 mask 作用一个重数字 w
unsigned int apply_heavy(unsigned int mask, int w) {
    unsigned int next_mask = 0;
    if (w > TARGET) w = TARGET + 1; // Cap the value
    for (int i = 0; i <= TARGET; ++i) {
        if ((mask >> i) & 1) {
            if (i + w <= TARGET) {
                next_mask |= (1 << (i + w));
            }
            if (1LL * i * w <= TARGET) {
                next_mask |= (1 << (1LL * i * w));
            }
        }
    }
    return next_mask;
}


void solve() {
    int u, v;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs1(1, 0, 0);
    dfs2(1, 1);
    build_seg(1, 1, n);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            
            int ancestor = lca(l, r);
            int heavy_nodes_count = query_path_count(l, r);
            
            if (heavy_nodes_count > HEAVY_THRESHOLD) {
                cout << 0 << "\n";
                continue;
            }

            if (heavy_nodes_count == 0) {
                if (a[l] == 1) {
                    cout << (dist(l, r) + 1 == TARGET) << "\n";
                } else {
                     cout << (a[l] + dist(l, r) == TARGET) << "\n";
                }
                continue;
            }
            
            vector<int> path;
            vector<int> path_l, path_r;
            int cur_l = l, cur_r = r;

            // 提取 l -> lca 的路径
            while(top[cur_l] != top[ancestor]){
                path_l.push_back(cur_l);
                cur_l = parent[top[cur_l]];
            }
            while(cur_l != ancestor){
                path_l.push_back(cur_l);
                cur_l = parent[cur_l];
            }
            path_l.push_back(ancestor);

            // 提取 r -> lca 的路径
            while(top[cur_r] != top[ancestor]){
                path_r.push_back(cur_r);
                cur_r = parent[top[cur_r]];
            }
            while(cur_r != ancestor){
                path_r.push_back(cur_r);
                cur_r = parent[cur_r];
            }
            
            path = path_l;
            reverse(path_r.begin(), path_r.end());
            path.insert(path.end(), path_r.begin(), path_r.end());

            unsigned int mask = 0;
            if (a[path[0]] <= TARGET) {
                mask = (1 << a[path[0]]);
            }

            for (size_t i = 1; i < path.size(); ++i) {
                int val = a[path[i]];
                if (val > TARGET + 1) val = TARGET + 1;

                mask = apply_heavy(mask, val);
            }
            
            cout << ((mask >> TARGET) & 1) << "\n";

        } else {
            int x, d;
            cin >> x >> d;
            bool old_is_heavy = (a[x] > 1);
            bool new_is_heavy = (d > 1);
            if (old_is_heavy != new_is_heavy) {
                update_seg(1, 1, n, dfn[x], new_is_heavy ? 1 : -1);
            }
            a[x] = d;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

代码说明喵~ 上面的代码为了简洁和清晰，在查询稀疏路径时，我没有用get_path_heavy_nodes提取重节点再计算中间的1，而是直接暴力提取了整条路径上的所有节点来进行DP。因为当重节点数量很少时，路径的总长度通常也不会太长，这样做可以简化代码逻辑，并且对于这道题的数据范围是可以通过的。如果遇到更极限的数据，使用get_path_heavy_nodes并计算中间1的个数进行DP会是更稳妥的方案！

复杂度分析

时间复杂度:
- 预处理: 树链剖分 $O(N)$ ，建立线段树 $O(N)$ 。总共是 $O(N)$ 。
- 修改操作: 在线段树上单点修改，复杂度为 $O(\log N)$ 。
- 查询操作:
  - 统计路径重节点数：树链剖分将路径分为 $O(\log N)$ 段，每段在线段树上查询是 $O(\log N)$ ，总共 $O(\log^2 N)$ 。
  - 提取路径并DP：当路径稀疏时，我们提取整条路径。路径长度最长为 $N$ 。DP的复杂度是 $O(\text{路径长度} \times \text{TARGET})$ 。虽然最坏是 $O(N)$ , 但只有在重节点数很少（总和也小）的情况下才会执行，此时路径长度一般也受限，所以均摊下来很快。
- 综合来看，查询操作的瓶颈在于路径查询，复杂度是 $O(\log^2 N)$ 到 $O(N)$ 之间，但可以通过本题。
空间复杂度:
- 树链剖分和线段树都需要 $O(N)$ 的空间。总空间复杂度为 $O(N)$ 。

知识点总结

这真是一道精彩的题目，融合了好多知识点呢，喵！

问题简化与观察: 解决复杂问题的突破口往往在于发现题目中隐藏的“弱点”。本题的“弱点”就是目标值 24 非常小，这使得我们可以把状态压缩到很小的范围内。
位掩码DP (Bitmask DP): 当状态空间不大，且每个状态是“是/否”集合时，位掩码是非常高效的表示方式。
树链剖分 + 线段树: 处理树上路径修改和查询的通用强力武器。将树上问题转化为序列问题是其核心思想。
剪枝与分类讨论: 通过分析“重数字”的性质，我们发现可以快速排除掉绝大多数不可能的情况，只对少数“棘手”的情况进行详细计算。这是算法竞赛中非常重要的优化思想。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，喵~！

E - Echoes of 24 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心问题：如何得到 24？ ​

关键观察：1 的特殊性与稀疏的“有效数字” ​

终极武器：树链剖分 + 线段树 ​

整合起来的完整算法 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​