树中的相似对
这是来自Hackerrank竞赛的一个问题：
您将得到一棵树，其中每个节点被标记为1，2，…。在这棵树中有多少相似的对(S)？
A (A，B)是一个相似的对当且仅当
- 节点A是节点B的祖先
- abs(A ) <= 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)
现在，蛮力方法解决了大约一半的测试用例，但对于另一半，它只是简单地慢下来。我试图通过存储节点子树的间隔来扩展algo，从而能够消除一些分支，但总体上只是多了几个点。
对于如何有效地解决这个问题，有什么想法吗？
回答 3
Stack Overflow用户
发布于 2013-05-12 08:59:30
这个解决方案怎么样？
按预先顺序遍历树(如DFS)，并维护多集S以进行查询。
输入节点x时，只需将x添加到S中即可。在离开节点x时(在此上下文中，我指的是在访问x的所有子节点之后的某个时间)，从S中删除x。通过这样做，在树遍历过程中的所有时间，您都有x在S中的所有祖先。
现在，让我们计算一个元素为x的相似对。另一个元素(例如y)必须位于S中(因为它必须是x的祖先)，并且它必须保存该x - T <= y <= x + T。有多少这样的S？是的，您只需查询S，就可以在 [x-T, x+T].之间计算值中的元素数。这个查询可以在O(log )时间内回答，因为S中的元素数永远不会超过N。
更具体地说，这种数据结构的候选对象是BST或其他类似的树数据结构(例如AVL-树、RB-树、Treap等)。支持添加和删除操作。或者，芬威克树或段树也可以在O(log )时间内查询这些查询。
总之，通过维护当前访问节点的所有祖先，并总结成对的数量(包括当前节点)，您可以找到所有相似节点的数量。由于我们对树中的每个节点都有一个查询，所以总的时间复杂度是O(N log )。
Stack Overflow用户
发布于 2013-05-12 08:44:07
我将尝试对树进行深度优先搜索，使用二进制索引树(请参阅Topcoder教程 )来存储堆栈中看到的所有值。
这允许您对所需范围内的父节点数量进行O(log(n))查询，因此总的复杂性将是O(nlog(n))
Stack Overflow用户
发布于 2016-01-29 15:53:23
我用地图做的。您只需为每个节点保存父节点，然后递归计算每个节点的相似对。
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);
}
}https://stackoverflow.com/questions/16505216
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号