Weekly Contest 454

欢迎大家加QQ群：623375442。周赛题解都会在周日下午3点左右发布。欢迎继续关注。这周题目确实不太难。

3582. Generate Tag for Video Caption

给你一个字符串 caption，表示一个视频的标题。

需要按照以下步骤 按顺序 生成一个视频的 有效标签 ：

1. 将 所有单词 组合为单个 驼峰命名字符串 ，并在前面加上 '#'。驼峰命名字符串 指的是除第一个单词外，其余单词的首字母大写，且每个单词的首字母之后的字符必须是小写。
2. 移除 所有不是英文字母的字符，但 保留 第一个字符 '#'。
3. 将结果 截断 为最多 100 个字符。

对 caption 执行上述操作后，返回生成的 标签 。

测试样例：

输入：caption = "Leetcode daily streak achieved"

输出："#leetcodeDailyStreakAchieved"

解释：除了 "leetcode" 以外的所有单词的首字母需要大写。

解答：

1. 整体流程：可以拆成三步：先清洗并进行驼峰化（remove 方法 + combine 方法），再截断（truncate 方法）。
2. remove 方法：
   • 目标是：移除所有非英文字母字符，同时通过标记（upCase 标志）来决定下一个合法字母是否需要大写，以便组合单词。
   • 遍历原始 caption 的每个字符：
     • 如果是字母：如果前面曾遇到非字母（upCase = true），则需要把当前字母转换成大写形式；否则直接按原字符或做相应大小写转换：这里代码中还做了“如果本身是大写且不需要大写，则转为小写”的处理，是为了统一后面的驼峰需求（保证第一个单词小写、后续首字母大写，其余小写）。
     • 如果不是字母：将 upCase 置为 true，表示下一个合法字母需要大写；且不向结果追加任何字符。
   • 最终返回一个只含字母的新字符串，且已在字符转换上部分考虑了驼峰拼接的需求。
3. combine 方法：
   • 在前面加上 #，并确保第一个单词（即 remove 结果的前缀部分）首字母小写。如果 remove 结果首字母本身是大写，则先把它转为小写，再 append 后面的部分；否则直接 append 整个 remove 结果。
   • 这样得到初步的 #camelCase 格式字符串。
4. truncate 方法：
   • 如果长度超过 100，则直接取前 100 个字符，否则原样返回。
5. 注意：题目说“将所有单词组合为单个驼峰命名字符串”，remove 中通过非字母触发 upCase=true，实现单词边界检测。combine 中再加上 # 并调整首字母。

class Solution {
    public String generateTag(String caption) {
        // 依次执行：先 remove 清洗与驼峰标记 -> combine 加 '# ' 并调整首字母 -> truncate 截断至最多 100 字符
        return truncate(combine(remove(caption)));
    }

    /**
     * 清洗 caption：移除所有非英文字母字符，同时根据单词边界（遇到非字母）决定下一个字母是否大写。
     * 具体做法：
     * - 使用 StringBuilder sb 保存处理结果；
     * - upCase 标志表示：如果 true，则当前合法字母要大写；否则按原情况，但若本身是大写且不需要大写，则转为小写，以便后续驼峰逻辑。
     */
    private String remove(String caption) {
        StringBuilder sb = new StringBuilder();
        boolean upCase = false;  // 是否需要把当前字母转为大写
        for (int i = 0; i < caption.length(); ++i) {
            char c = caption.charAt(i);
            if (Character.isLetter(c)) {
                // 是字母：根据 upCase 决定转换
                if (upCase && Character.isLowerCase(c)) {
                    // 之前遇到非字母，下一个字母需要大写
                    sb.append((char) (c - 'a' + 'A'));
                } else if (!upCase && Character.isUpperCase(c)) {
                    // 当前不需要大写，但字符本身是大写，将其转为小写（保证第一个单词或非边界字母都是小写）
                    sb.append((char) (c - 'A' + 'a'));
                } else {
                    // 其他情况，直接按原字符添加（要么本来大写且需要大写，要么本来小写且不需要大写）
                    sb.append(c);
                }
                // 添加后，重置 upCase
                upCase = false;
            } else {
                // 非字母：标记下一个字母要大写，但本身不 append
                upCase = true;
            }
        }
        // 返回只含字母且已部分做驼峰首字母大小写转换的字符串
        return sb.toString();
    }

    /**
     * 组合成带 '#' 的驼峰字符串：
     * - 在前面 append '#'
     * - 如果 remove 结果首字母是大写，则先转为小写，以保证第一个单词小写；否则直接 append
     */
    private String combine(String caption) {
        StringBuilder sb = new StringBuilder();
        sb.append('#');
        if (caption.length() > 0 && Character.isUpperCase(caption.charAt(0))) {
            // 首字母大写，转为小写后再 append 后续
            sb.append((char) (caption.charAt(0) - 'A' + 'a'));
            sb.append(caption.substring(1));
        } else {
            // 直接 append
            sb.append(caption);
        }
        return sb.toString();
    }

    /**
     * 如果长度超过 100，截断至 100 字符；否则直接返回
     */
    private String truncate(String caption) {
        if (caption.length() > 100) {
            return caption.substring(0, 100);
        } else {
            return caption;
        }
    }
}

3583. Count Special Triplets

给你一个整数数组 nums。

特殊三元组 定义为满足以下条件的下标三元组 (i, j, k)：

• 0 <= i < j < k < n，其中 n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

返回数组中 特殊三元组 的总数。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

测试样例：

输入：x = nums = [6,3,6]

输出：1

解释：唯一的特殊三元组是 (i, j, k) = (0, 1, 2)

解答：

1. 把 j 视为“中间”点：条件要求 nums[i] 和 nums[k] 都等于 nums[j] 2。即 i < j < k，且 nums[i] = 2 nums[j]，nums[k] = 2 * nums[j]。
2. 用哈希计数：
   • 维护两个哈希表：left 用于记录已经遍历过的元素出现次数；right 用于记录还未遍历到的元素出现次数。
   • 初始时，right 记录数组中所有元素的频次；left 为空。
3. 遍历 j 位置：
   • 对于当前值 n = nums[j]，先从 right 中将其频次减 1，表示此位置作为中间点，不再视作“后面可选的 k”。
   • 计算 lc = left.getOrDefault(n 2, 0)，即 i 位置上满足 nums[i] == 2 n 的已有个数。
   • 计算 rc = right.getOrDefault(n 2, 0)，即 k 位置上满足 nums[k] == 2 n 的后续个数。
   • 对结果 res += lc * rc（可能很大，需取模）。
   • 然后将当前元素计入 left（left.put(n, left.getOrDefault(n,0)+1)），以便后续作为 i 参与更右侧 j。

class Solution {
    private static final int mod = 1_000_000_007;

    public int specialTriplets(int[] nums) {
        // left 存储遍历过的元素频次，right 存储还未遍历的元素频次
        HashMap<Integer, Integer> left = new HashMap<>(), right = new HashMap<>();
        // 初始化 right：统计所有 nums 中的频次
        for (int n : nums) {
            right.put(n, right.getOrDefault(n, 0) + 1);
        }
        long res = 0;
        // 遍历每个位置 j，将 nums[j] 作为中间点
        for (int n : nums) {
            // 当前位置不再作为后续 k，先在 right 中减去
            right.put(n, right.get(n) - 1);
            // 计算左侧 i 满足 nums[i] == 2*n 的个数
            long lc = left.getOrDefault(n * 2, 0);
            // 计算右侧 k 满足 nums[k] == 2*n 的个数
            long rc = right.getOrDefault(n * 2, 0);
            // 所有组合数累加到结果，并取模
            res = (res + lc * rc % mod) % mod;
            // 然后将当前元素纳入 left，以便其后可作为 i
            left.put(n, left.getOrDefault(n, 0) + 1);
        }
        // 返回结果
        return (int) res;
    }
}

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

给你一个整数数组 nums 和一个整数 m。

返回任意大小为 m 的 子序列 中首尾元素乘积的最大值。

子序列 是可以通过删除原数组中的一些元素（或不删除任何元素），且不改变剩余元素顺序而得到的数组。

测试样例：

输入：nums = [-1,-9,2,3,-2,-3,1], m = 1

输出：81

解释：子序列 [-9] 的首尾元素乘积最大：-9 * -9 = 81。因此，答案是 81。

解答：

1. m == 1 特例：如果子序列长度为 1，则首尾相同，乘积为 n n。只需要遍历一次数组，选取绝对值最大的数（平方后最大）。实际上代码直接对每个 n 计算 nn 并取最大即可。
2. m > 1 情况：
   • 思路：枚举子序列的第一个元素在原数组中的位置 i，设该元素值为 cur = nums[i]。剩下要再从后面的元素中选出 m-1 个元素，使得末尾元素（最后一个选的元素）与 cur 相乘得到最大值。对于给定 i 作为首元素，最佳的末尾元素要么是剩余可选元素中的最小值，要么是最大值（因为负负得正或正正得正、负正得负；需要综合考虑）。
   • 直接枚举组合会爆炸。巧妙做法是用一个 TreeMap<Integer, Integer> map 来维护“从当前位置 i+1 到末尾剩余未删除的元素”的多重集合（频次数），这样可以快速获取最小键 firstKey() 和最大键 lastKey()。
   • 同时使用双指针 i 和 right：right 用来保证“从 i 位置到 right-1 位置的元素已经被从 map 中删除”，从而确保 map 中只剩下“可在首元素 i 之后选取的位置 ≥ i+1 且后续还能凑足 m-1 个元素”的候选池。
3. 具体逻辑：
   • 先初始化 map 记录整个数组所有元素出现次数。
   • 用 right = 0 作为右指针，i 从 0 遍历到 n-1。对于每个 i：
     • 移动 right：只要 right < n 且 right - i + 1 < m，表示从 i 到 right 位置共有 (right - i + 1) 个元素，如果还小于 m，说明以 i 为首元素，要保证后面至少有 m-1 个元素可用，因此需要把更多位置从 map 中删除，即将 nums[right] 的计数在 map 中减 1（因为这些位置早于“候选尾部”），然后 right++。这样循环结束后，确保 [i..right-1] 一段已经移除，剩下的位置数 ≥ m-1，可以从 map 中任选。
     • 如果 map.isEmpty()，说明后面没有可选元素，直接跳出循环。
     • 此时 map.firstKey()、map.lastKey() 分别是剩余可选元素的最小值和最大值。对于首元素 cur = nums[i]，最佳尾部要么 cur firstKey()，要么 cur lastKey()，取两者中较大值更新 res。
   • 继续下一个 i，并将 i 位置的元素已被从 map 中减过（前面移动 right 时），循环自然继续。
4. 注意：这样的做法在每个 i 位置都能以 O(log n) 时间获取最小/最大候选尾部，实现整体 O(n log n) 复杂度（因为 TreeMap 的增删和取首尾键均为 O(log n)）。

class Solution {
    public long maximumProduct(int[] nums, int m) {
        long res = Long.MIN_VALUE;
        // 特例：m == 1 时，子序列只有一个元素，首尾同一个，乘积 = n*n
        if (m == 1) {
            for (long n : nums) {
                res = Math.max(res, n * n);
            }
        } else {
            // TreeMap 用来维护候选尾部元素的多重集合（value: 频次）
            TreeMap<Integer, Integer> map = new TreeMap<>();
            // 初始化：把所有 nums 中的元素加入 map
            for (int n : nums) {
                map.put(n, map.getOrDefault(n, 0) + 1);
            }
            int right = 0;
            int n = nums.length;
            // 枚举每个位置 i 作为子序列首元素
            for (int i = 0; i < n; ++i) {
                // 移动 right，保证已移除的元素个数使得剩余可选位置 ≥ m-1
                // 具体逻辑：从 i 到 right-1 这些位置被认为“已过期”而从 map 中删除
                // 只要当前区间长度 < m，就继续扩展 right 并删除相应元素
                while (right < n && right - i + 1 < m) {
                    // 把 nums[right] 从 map 中移除一份（因其位置太靠前，无法作为尾部）
                    int c = map.get(nums[right]);
                    if (c == 1) {
                        map.remove(nums[right]);
                    } else {
                        map.put(nums[right], c - 1);
                    }
                    ++right;
                }
                // 如果此时候选池为空，则没有足够元素可选，提前结束
                if (map.isEmpty()) break;
                // 剩余可选元素中的最小值和最大值
                int first = map.firstKey();
                int last = map.lastKey();
                long cur = nums[i];  // 当前首元素值
                // 计算两种候选尾部的乘积，选较大者
                res = Math.max(res, Math.max(cur * first, cur * last));
                // 注意：下一个循环 i+1 时，i 位置元素已在前面某次 right 移动时被删除或应当被删除。
                // 但如果 right <= i，则需要手动删除当前 i 位置，以保持后续候选池正确。
                // 实际上本实现依赖 right 随 i 推进时，会在合适时机移除 nums[i]。
                // 这里无需显式操作，因为当 i 增加时 right 也会随 window 条件自动推进并删除相应元素。
            }
        }
        return res;
    }
}

3585. Find Weighted Median Node in Tree

给你一个整数 n，以及一棵 无向带权 树，根节点为节点 0，树中共有 n 个节点，编号从 0 到 n - 1。该树由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示存在一条从节点 ui 到 vi 的边，权重为 wi。

带权中位节点 定义为从 ui 到 vi 路径上的 第一个 节点 x，使得从 ui 到 x 的边权之和 大于等于 该路径总权值和的一半。

给你一个二维整数数组 queries。对于每个 queries[j] = [uj, vj]，求出从 uj 到 vj 路径上的带权中位节点。

返回一个数组 ans，其中 ans[j] 表示查询 queries[j] 的带权中位节点编号。

测试样例：

输入：n = 2, edges = [[0,1,7]], queries = [[1,0],[0,1]]

输出：[0,1]

解释：	查询	路径	边权	总路径权值和	一半	解释	答案
[1, 0]	1 → 0	[7]	7	3.5	从 1 → 0 的权重和为 7 >= 3.5，中位节点是 0。	0
[0, 1]	0 → 1	[7]	7	3.5	从 0 → 1 的权重和为 7 >= 3.5，中位节点是 1。	1

解答：

1. 预处理——树的 LCA（二进制提升）：
   • 构建邻接表表示树，每条边带权 w。
   • 从根 0 开始 DFS，记录每个节点到根的距离 dist（累积权重）、深度 depth、以及父节点 up[0] 及经过该父节点的边权 sumUp[0]。
   • 预先计算 LOG = ceil(log2(n)) 层数，然后填二进制提升表：
     • up[k][node] 表示从 node 向上跳 2^k 步到的祖先节点。
     • sumUp[k][node] 表示沿这 2^k 跳跃所经过边的总权重。
   • 这样可以在 O(log n) 内查询任意两个节点的 LCA，并在跳跃时获取路径权重累积等信息。
2. 回答每个查询：
   • 设查询节点 u, v。先求两者的 LCA 节点 anc。
   • 计算 dist(u, v) = dist[u] + dist[v] - 2 * dist[anc]，即整条路径的总权重。
   • 设 half = (total + 1) / 2，代表所需的最小权重阈值；从 u 出发沿路径，找第一个累积距离 ≥ half 的节点。
   • 分两种情况：
     1. 带权中位点在 u 到 anc 这段向上的部分：如果从 u 到 anc 的距离 distUL = dist[u] - dist[anc] ≥ half，说明中位点在这条向上路径上。在这条路径上，需要找到离 u 最近的那个节点使得距离 ≥ half。使用 liftOnPathUp(u, anc, half) 方法：
        • 从 u 往上二进制提升：维护已累计距离 currSum，从高位跳跃开始尝试，如果跳跃后累计距离仍 < half 且不会超过 anc，就跳，否则不跳，直到最后一步再跳一格到满足位置。
     2. 带权中位点在 anc 到 v 这段“向下”部分：说明 dist(u, anc) < half，需继续从 anc 往 v 方向走 rem = half - dist(u, anc) 距离才能达到阈值。路径方向是从 anc 到 v。可以转换成：从 v 往上走，在路径上找第一个距离 v 的累积权重 ≤ allowed = dist(v, anc) - rem 的最深节点，它即是答案。使用 liftOnPathUpLimited(v, anc, allowed)：
        • 该方法从 v 向上二进制提升，维护累计距离 currSum，只要加上某个跳跃距离 ≤ allowed，就跳；最终得到满足条件的最深节点。
   • 将上述得到的节点编号放入结果数组。
3. 核心方法：
   • findLCA(u, v): 标准二进制提升先把深度高的点提到同深度，然后从高位逐层同时提，最后返回父节点。
   • jump(u, diff): 从 u 往上跳 diff 层。
   • liftOnPathUp(u, anc, half): 从 u 往上，寻找累积距离首次达到 ≥ half 的节点，保证不超过 anc。
   • liftOnPathUpLimited(v, anc, allowed): 从 v 往上，寻找累积距离 ≤ allowed 的最深节点，保证不超过 anc。

class Solution {
    public int[] findMedian(int n, int[][] edges, int[][] queries) {
        // 构造 LCA 结构，内部做 DFS 初始化 dist、depth、up[0]、sumUp[0]，并做二进制提升表
        LCA lca = new LCA(n, edges);
        int[] res = new int[queries.length];
        int pos = 0;
        // 对每个查询 u,v 计算带权中位节点
        for (int[] q : queries) {
            int u = q[0], v = q[1];
            // 找到 LCA 节点
            int anc = lca.findLCA(u, v);
            // distU, distV 是到根的距离，distAnc 是 anc 到根的距离
            long distU = lca.ancestors[u].dist;
            long distV = lca.ancestors[v].dist;
            long distAnc = lca.ancestors[anc].dist;
            // 路径总权重 = dist(u,root) + dist(v,root) - 2 * dist(anc,root)
            long total = distU + distV - 2 * distAnc;
            // half 阈值，若 total 为奇数，(total+1)/2 向上取整效果
            long half = (total + 1) / 2;
            // 从 u 到 anc 的距离
            long distUL = distU - distAnc;
            if (distUL >= half) {
                // 中位点在 u→anc 这段路径上，调用 liftOnPathUp 找到第一个满足累计距离 ≥ half 的节点
                res[pos++] = lca.liftOnPathUp(u, anc, half);
            } else {
                // 中位点在 anc→v 这段路径上
                // rem：从 anc 出发继续还需走的距离
                long rem = half - distUL;
                // dist(v,anc) = distV - distAnc
                long distVL = distV - distAnc;
                // allowed：转换成从 v 往上找距离 ≤ allowed 的最深节点
                long allowed = distVL - rem; // >= 0
                res[pos++] = lca.liftOnPathUpLimited(v, anc, allowed);
            }
        }
        return res;
    }
}

// 二进制提升 + 距离信息的 LCA 结构
class LCA {
    Ancestor[] ancestors;  // 存储每个节点的 up[], sumUp[], depth, dist
    int LOG; // 最大提升层数

    public LCA(int n, int[][] edges) {
        ancestors = new Ancestor[n];
        // 计算需要的二进制提层数，2^LOG >= n
        LOG = 32 - Integer.numberOfLeadingZeros(n);
        // 构建邻接表
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; ++i) {
            graph[i] = new ArrayList<>();
            ancestors[i] = new Ancestor(LOG);
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            graph[u].add(new int[]{v, w});
            graph[v].add(new int[]{u, w});
        }
        // 从根 0 开始 DFS：parent = -1，depth = 0，dist = 0，incoming weight = 0
        dfs(0, -1, 0, 0L, 0, graph);
        // 构建二进制提升表 up[k] 和 sumUp[k]
        for (int k = 1; k < LOG; ++k) {
            for (int node = 0; node < ancestors.length; ++node) {
                int mid = ancestors[node].up[k - 1];
                if (mid < 0) {
                    // 没有 2^{k-1} 祖先
                    ancestors[node].up[k] = -1;
                    ancestors[node].sumUp[k] = 0L;
                } else {
                    // 有中间祖先，则 up[k] = mid 的 up[k-1]
                    ancestors[node].up[k] = ancestors[mid].up[k - 1];
                    // sumUp[k] 是 node -> mid 的距离 + mid -> up[k] 的距离
                    ancestors[node].sumUp[k] = ancestors[node].sumUp[k - 1] + ancestors[mid].sumUp[k - 1];
                }
            }
        }
    }

    /**
     * DFS 初始化每个节点的 depth、dist、up[0]、sumUp[0]
     * @param cur 当前节点
     * @param parent 父节点
     * @param depth 深度
     * @param dist 从根到当前节点的累积距离
     * @param wFromParent 从父节点到当前节点的边权
     * @param graph 邻接表
     */
    private void dfs(int cur, int parent, int depth, long dist, int wFromParent, List<int[]>[] graph) {
        ancestors[cur].depth = depth;
        ancestors[cur].dist = dist;
        ancestors[cur].up[0] = parent;
        // sumUp[0] 存储从 cur 往上跳 1 步到 parent 的边权
        ancestors[cur].sumUp[0] = (parent == -1 ? 0L : wFromParent);
        for (int[] nei : graph[cur]) {
            int nxt = nei[0], w = nei[1];
            if (nxt == parent) continue;
            // 下一层：深度+1，累积距离 dist + w，记录 incoming weight w
            dfs(nxt, cur, depth + 1, dist + w, w, graph);
        }
    }

    /**
     * 找 LCA
     */
    public int findLCA(int u, int v) {
        // 保证 u.depth >= v.depth
        if (ancestors[u].depth < ancestors[v].depth) {
            int tmp = u; u = v; v = tmp;
        }
        // 将 u 提到和 v 同深度
        int diff = ancestors[u].depth - ancestors[v].depth;
        u = jump(u, diff);
        if (u == v) return u;
        // 同时从高位往下尝试提升，直到两者父节点相同
        for (int k = LOG - 1; k >= 0; --k) {
            int au = ancestors[u].up[k];
            int av = ancestors[v].up[k];
            if (au != av) {
                u = au;
                v = av;
            }
        }
        // 此时 u 和 v 父节点即为 LCA
        return ancestors[u].up[0];
    }

    /**
     * 从节点 u 向上跳 diff 层
     */
    public int jump(int u, int diff) {
        for (int k = 0; k < LOG; ++k) {
            if (u < 0) break;
            if (((diff >> k) & 1) != 0) {
                u = ancestors[u].up[k];
            }
        }
        return u < 0 ? -1 : u;
    }

    /**
     * 从 u 往上到 anc 的路径上，寻找第一个使得 dist(u, x) >= half 的节点 x
     * 假设 dist(u, anc) >= half。采用二进制提升贪心跳跃：
     * - currSum 记录已累计距离，curr 记录当前位置
     * - 从高位 k 从大到小尝试：如果向上跳 2^k 步后仍然在 anc 之下，且 currSum + sumUp[k] < half，则跳；否则不跳
     * - 最后跳一步到第一个 ≥ half 的节点
     */
    public int liftOnPathUp(int u, int anc, long half) {
        long currSum = 0L;
        int curr = u;
        // 从大 k 开始尝试跳跃
        for (int k = LOG - 1; k >= 0; --k) {
            int next = ancestors[curr].up[k];
            // next 需合法且深度不小于 anc.depth，保证不越过 anc
            if (next >= 0 && ancestors[next].depth >= ancestors[anc].depth) {
                long w = ancestors[curr].sumUp[k];
                if (currSum + w < half) {
                    // 若跳后累计距离仍 < half，就跳
                    currSum += w;
                    curr = next;
                }
            }
        }
        // 目前 currSum < half，且 curr 已是能跳的最远（若跳一步可能 ≥ half）
        if (curr != anc) {
            // 再跳一步父节点，必然使距离达到或超过 half
            int par = ancestors[curr].up[0];
            curr = par;
        }
        return curr;
    }

    /**
     * 在 anc→v 路径上找带权中位。转换思路：在 v→anc 路径上，寻找距离 v 累积 ≤ allowed 的最深节点
     * rem 表示从 anc 开始还需走 rem 距离；dist(v,anc) = D；allowed = D - rem。
     * 从 v 向上跳：如果 currSum + sumUp[k] ≤ allowed，则跳。
     */
    public int liftOnPathUpLimited(int v, int anc, long allowed) {
        long currSum = 0L;
        int curr = v;
        // 从高位 k 逐层尝试向上跳
        for (int k = LOG - 1; k >= 0; --k) {
            int next = ancestors[curr].up[k];
            if (next >= 0 && ancestors[next].depth >= ancestors[anc].depth) {
                long w = ancestors[curr].sumUp[k];
                if (currSum + w <= allowed) {
                    currSum += w;
                    curr = next;
                }
            }
        }
        // curr 即为满足 dist(v,curr) ≤ allowed 的最深节点，也对应 anc→v 路径上 dist(anc,x) ≥ rem 的第一个节点
        return curr;
    }
}

// 用于存储每个节点的二进制提升信息及距离等
class Ancestor {
    int[] up;       // up[k]：节点向上 2^k 步的祖先
    long[] sumUp;   // sumUp[k]：从该节点向上 2^k 步过程中边权和
    int depth;      // 深度（相对于根 0）
    long dist;      // 从根到该节点的累积距离
    public Ancestor(int len) {
        up = new int[len];
        sumUp = new long[len];
        Arrays.fill(up, -1);
        Arrays.fill(sumUp, 0L);
    }
}