1

这是 Hackerrank 竞赛中的一个问题：

给你一棵树，其中每个节点都标记为 1、2、...、n。这棵树中有多少个相似的对（S）？

一对 (A,B) 是相似对当且仅当

  • 节点 A 是节点 B 的祖先
  • 绝对（A - B）<= T。

输入格式：输入的第一行包含两个整数 n 和 T。接下来是 n-1 行，每行包含两个整数 si 和 ei，其中节点 si 是节点 ei 的父节点。

输出格式：输出一个整数，表示树中相似对的数量

约束：

1 <= n <= 100000  
0 <= T <= n  
1 <= si, ei <= n.

也保证没有循环，但树不必是二叉树。

样本输入：

5 2
3 2
3 1
1 4
1 5

样本输出：

4

解释：相似的对是：(3, 2) (3, 1) (3, 4) (3, 5)

现在，蛮力方法解决了大约一半的测试用例，但对于另一半来说，它只是放慢速度。我试图通过存储节点的子树的间隔来扩展算法，从而能够消除一些分支，但总体上只是多了几个点。

关于如何有效解决此搜索的任何想法？

4

4 回答 4

4

那么，这个解决方案怎么样？

按前序遍历树（如 DFS），并维护一个多集S以进行查询。

在进入节点x时，只需添加x到S. 在离开节点x时（在这种情况下，我的意思是在x访问完所有子节点之后的时间），x从S. 通过这样做，在树遍历期间的所有时间内，您都拥有in的所有祖先xS。

现在让我们计算一个元素为 的相似对x。另一个元素（比如y）必须位于S（因为它必须是 的祖先x），并且它必须持有x - T <= y <= x + T。有多少这样y的？是的，您可以只查询S来计算value between的元素数量S[x-T, x+T]。这个查询可以在 O(log N) 时间内回答，因为元素的数量S永远不会超过 N。

更具体地说，该数据结构的候选者是BST或其他支持添加和删除操作的类似树数据结构（例如 AVL-tree、RB-tree、Treap 等）。或者，Fenwick Tree或Segment Tree也可以在 O(log N) 时间内完成这些查询。

综上所述，通过维护当前访问节点的所有祖先，并将对的数量（包括当前节点）求和，可以找到所有相似对的数量。由于我们对树中的每个节点都有一个查询，因此总体时间复杂度为O(N log N)。

于 2013-05-12T08:59:30.120 回答
1

我会尝试对树进行深度优先搜索，使用二叉索引树（请参阅Topcoder 教程）来存储堆栈中看到的所有值。

这允许您对所需范围内的父节点数进行 O(log(n)) 查询，因此总体复杂度将为 O(nlog(n))

于 2013-05-12T08:44:07.877 回答
1

我是用地图做的。您只需为每个节点保存父节点，然后递归计算每个节点的相似对。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution
{

    static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    static int similarPairs = 0;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int totalRows = sc.nextInt();
        int T = sc.nextInt();

        for (int i = 0; i < totalRows - 1; i++)
        {
            int data = sc.nextInt();
            int cdata = sc.nextInt();
            int currValue = cdata;

            map.put(cdata, data);

            while (map.get(cdata) != null)
            {

                int parent = map.get(cdata);

                if (Math.abs(parent - currValue) <= T)
                {
                    similarPairs += 1;
                }

                cdata = parent;
            }
        }

        System.out.println(similarPairs);
    }
}
于 2016-01-29T15:53:23.507 回答
0

下面的内容怎么样，可以在低级 C 中实现，而不需要任何列表/字典/循环结构，例如哈希表。

  1. 读取输入数据，存储每个解析的行，并计算出一个节点可以拥有的最大子节点数 M
  2. 分配 的整数数组int[] arr_of_ints = new int[n*M]，并将所有条目初始化为 0。想法是节点 i（其中 1<=i<=n）对应于 M 个整数 arr_of_ints[M*(i-1)] 到 arr_of_ints[M *i]，并且这些条目的值是该节点的子节点
  3. 遍历保存的解析数据，并填写arr_of_ints，计算出哪个节点在顶部
  4. 分配一个数组int[] ancestors = new int[n]，它将存储所有祖先的值
  5. 最后，从树的顶部开始，使用递归函数向下遍历树，使用数组ancestors，这样在每个节点处就不需要遍历树来计算相似节点的数量。你的递归越深，你在数组中越远ancestors，但是当你到达分支的末端时，这个位置就会展开
据我所知，如果有足够的内存供 arr_of_ints[M*i] 使用，那么它应该尽可能快。

更新：我已经用 C# 编写了我的解决方案的一个版本，见下文，我认为它是 O(n log n)。

class Solution {
    static char[] space = new char[] { ' ' };
    class FileRow {
        public readonly int parent;
        public readonly int child;
        public FileRow(string str) {
            string[] split = str.Split(space);
            parent = int.Parse(split[0]); child = int.Parse(split[1]);
        }
    }
    public static void Main(String[] args) {
        List<FileRow> inputdata = new List<FileRow>();
        StreamReader sr = File.OpenText("inputfile.txt");
        String[] split = sr.ReadLine().Split(space);
        int n = int.Parse(split[0]), T = int.Parse(split[1]);
        int[] arr = new int[n]; // this will record the max num of children
        while (!sr.EndOfStream) {
            FileRow fr = new FileRow(sr.ReadLine());
            arr[fr.parent - 1]++;
            inputdata.Add(fr);
        }
        sr.Close();
        int M = 0;
        for (int i = 0; i < arr.Length; i++) {
            M = Math.Max(M, arr[i]);
            arr[i] = 0;    // set all arr to zero, for use below in setting up tree
        }
        int[,] tree = new int[n, M];
        Boolean[] not_root_node = new bool[n];   // all entries automatically initialised to false
        foreach (FileRow fr in inputdata) {
            not_root_node[fr.child - 1] = true;  // indicate that node fr.child isn't the root node of the tree
            tree[fr.parent - 1, arr[fr.parent - 1]++] = fr.child;
        }
        int count = 0, node = 0;
        for (int i = 0; i < not_root_node.Length; i++) {
            if (!not_root_node[i]) {
                count++; node = i + 1;
            }
            arr[i] = 0;    // set all arr to zero, for use below in calculating result
        }
        if (count != 1) throw new Exception("ERROR, root node for tree not unique, count="+count.ToString());
        // int node is the root of the tree
        int level = 0, result = 0;
        int[] ancestors = new int[n];
        do {
            int j = arr[node - 1];
            int nextnode = (j < M ? tree[node - 1,j] : 0);
            if (nextnode == 0) {
                level--;
                if (level >=0) node = ancestors[level];
            } else {
                ancestors[level++] = node;                
                arr[node - 1]++;
                node = nextnode;
                for (int i = 0; i < level; i++) {
                    if (Math.Abs(ancestors[i] - node) <= T) result++;
                }
            }
        } while (level >= 0);
        System.Diagnostics.Trace.WriteLine(result);
    }
}
于 2013-05-12T10:30:48.630 回答