题目链接注意事项根据满二叉树的节点编号规则：若根节点编号为u，则其左子节点编号为u一个朴素的想法是：我们在DFS过程中使用两个哈希表分别记录每层深度中的最小节点编号和最大节点编号，两者距离即是当前层的宽度，最终所有层数中的最大宽度即是答案。而实现上，我们可以利用先DFS左节点，再DFS右节点的性质可知，每层的最左节点必然是最先被遍历到，因此我们只需要记录当前层最先被遍历到点编号（即当前层最小节点编号），并在DFS过程中计算宽度，更新答案即可。关于编号溢出问题，之所以溢出仍能AC是因为测试数组中没有同层内「宽度」左端点不溢出，右端点溢出，同时该层就是最大宽度的数据点。我们可以通过u=u-map.

题目链接注意事项根据满二叉树的节点编号规则：若根节点编号为u，则其左子节点编号为u一个朴素的想法是：我们在DFS过程中使用两个哈希表分别记录每层深度中的最小节点编号和最大节点编号，两者距离即是当前层的宽度，最终所有层数中的最大宽度即是答案。而实现上，我们可以利用先DFS左节点，再DFS右节点的性质可知，每层的最左节点必然是最先被遍历到，因此我们只需要记录当前层最先被遍历到点编号（即当前层最小节点编号），并在DFS过程中计算宽度，更新答案即可。关于编号溢出问题，之所以溢出仍能AC是因为测试数组中没有同层内「宽度」左端点不溢出，右端点溢出，同时该层就是最大宽度的数据点。我们可以通过u=u-map.

图论-虚拟节点分层建图Nya图最短路题目链接:VirtualJudgeAcwing题意:题解:\(a,b\)连一个\(w\)的边,是正常操作,这里有一个重要操作是\(a\)层和\(a+1\)层能直接传送,如果这里使用笨笨的建图方式,那么时间复杂度就是\(O(n^2)\),时间复杂度太高,不太行.这里有一个聪明的建图方法--->虚拟节点分层建图具体表示为:将\(a\)层和\(a+1\)层中间建立一个虚拟节点,然后将\(a\)层的所以节点指向虚拟节点,然后虚拟节点指向\(a+1\)层,这样就能实现在\(O(n)\)的时间复杂度情况下进行建图,时间可以接受具体可以看图:code#includeusi

图论-虚拟节点分层建图Nya图最短路题目链接:VirtualJudgeAcwing题意:题解:\(a,b\)连一个\(w\)的边,是正常操作,这里有一个重要操作是\(a\)层和\(a+1\)层能直接传送,如果这里使用笨笨的建图方式,那么时间复杂度就是\(O(n^2)\),时间复杂度太高,不太行.这里有一个聪明的建图方法--->虚拟节点分层建图具体表示为:将\(a\)层和\(a+1\)层中间建立一个虚拟节点,然后将\(a\)层的所以节点指向虚拟节点,然后虚拟节点指向\(a+1\)层,这样就能实现在\(O(n)\)的时间复杂度情况下进行建图,时间可以接受具体可以看图:code#includeusi