主页 / 问题 / 1516339
Accepted
EzioMercer
Asked:2023-04-28 19:08:53 +0000 UTC2023-04-28 19:08:53 +0000 UTC

如何找到具有一定权重的树中的路径数？

  • 772

Yandex 竞赛。问题 G. 树路径

问题链接： https: //contest.yandex.ru/contest/36783/problems/G

因为 您需要注册才能查看，所以为了方便我将文字写在这里

给定一个有根树的n顶点和一个数字X。每个顶点都有一个数字——它的权重

让我们称之为升序路径ai, p(a_i), p(p(a_i)), ...，其中p(a)是顶点的父级a。简单地说，上升路径是从某个顶点开始并向根移动（不一定到达它）的路径。路径可以由一个顶点组成

路径的权重是该路径上顶点的总权重。

查找具有权重的上升路径的数量X

限制：

  • 1 ≤ n ≤ 2 * 10^5
  • −10^9 ≤ X ≤ 10^9
  • p_i- 顶点父编号：0 ≤ p_i ≤ n − 1，或者−1如果它是根
  • w_i- 最高重量：−10^4 ≤ w_i ≤ 10^4

我是如何决定的：

我从数组（树）的末尾开始，并向总和添加权重。我开始循环，直到到达根并且总和不超过X，转到父级并重复之前的操作。循环结束后，我看和是否完全相等X，如果是，则将计数器加 1，否则什么都不做。在移动到下一个顶点之前，我重置总和

代码（交互式）：

class Vertex {
    constructor(weight, parent) {
        this.weight = weight;
        this.parent = parent;
    }
}

function getNumberOfUpgoingPaths(tree, x) {
    let count = 0;
    let sum = 0;
    
    for (let i = tree.length - 1; i >= 0; --i) {
        const vertex = tree[i];
        let parentIndex = vertex.parent;
        
        sum += vertex.weight;
        
        while(parentIndex !== -1 && sum < x) {
            const parentVertex = tree[parentIndex];
            
            sum += parentVertex.weight;
            
            parentIndex = parentVertex.parent;
        }
        
        if (sum === x) ++count;
        
        sum = 0;
    }
    
    return count;
}

// Обработка входных данных

const inputs = document.querySelector('#inputs');

const startAlgorithm = () => {
  console.clear();
  
  const tree = [];
  const [[countOfvertexes, x], ...vertexes] = inputs.value.split('\n').map(x => x.split(' ').map(Number));
  
  vertexes.forEach(vertex => tree.push(new Vertex(vertex[1], vertex[0])))
  
  console.log(getNumberOfUpgoingPaths(tree, x));
}

startAlgorithm();

inputs.addEventListener('input', startAlgorithm);
textarea {
  width: 90%;
  height: 400px;
}
<textarea id="inputs">6 3
-1 1
0 1
0 1
1 1
2 2
3 1</textarea>

如果要更改数据，则输入格式如下：

  • 第一行，前2个数字为顶点数和X（处理时忽略顶点数，但需要这样写，以免破坏数据输入格式）

  • 从第二行开始，列出顶点，其中左边的数字是父节点的数字，右边的数字是顶点的权重

问题：

在某些测试中（在 Yandex 中未显示在哪个测试中），它出现故障 - 返回错误结果。在我自己提出的测试中，该算法工作正常。请帮我找到推理中的错误，或者至少是一个测试用例，所有的东西都坏了，然后我想我可以自己修复错误

алгоритм

1 个回答

  1. Best Answer

    你错过了顶点权重可以是负的

    w_i - вес вершины: −10^4 ≤ w_i ≤ 10^4

    所以&& sum < x可以早点停下来。

    在效率方面——在上一个主题中你应该已经学到了一些东西。

    • 2

相关问题