精品课程网站建设论文,百度搜索排名优化,免费推广论坛,重庆做网站 熊掌号爆栈指递归中#xff0c;存储的信息量大于系统栈的内存。 信息量包括元素编号#xff0c;每一层中开的变量。 和递归的层数正相关。 #xff08;虽然noip一般开栈#xff09; 1.手写栈 while(top){ int xsta[top]; for(each son) if(has son){ //blablabla sta[top]son; h…爆栈指递归中存储的信息量大于系统栈的内存。 信息量包括元素编号每一层中开的变量。 和递归的层数正相关。 虽然noip一般开栈 1.手写栈 while(top){ int xsta[top]; for(each son) if(has son){ //blablabla sta[top]son; hd[x]e[i].nxt; } else{ //blablabla sta[top--]0; } } 可以用一个弧优化使得每次儿子回溯后父亲往下的边的访问直接继续。 这样复杂度就对了。 如果son回溯后在到下一个son之前还要做一些事情那就用个pair结构体什么的讨论一下情况即可。 2.bfs序求dfs序 用bfs求dfs序先序遍历序 相同点 先出来father的编号再出来son的编号。根节点都是1号。 区别子树连续访问pk儿子连续访问。 联系就差一个size bfs求bfs序再倒序记录每个点的size 然后遍历bfs序。 这时x的fa一定已经求出了dfs序。 如果上一个点的fa和这个点的fa不同那么x一定是x的fa的第一个儿子到了fa之后就先访问x。dfn[x]dfn[fa[x]]1 如果上一个点的fa和这个点的fa相同那么x一定是上一个点的后兄弟。dfn[x]dfn[las]size[las] 理解就是dfs时会先遍历las的整个子树。并且下一个就一定是x了。 3.本地手动开栈 #pragma GCC (-W1,--stack128000000)手动开栈。 转载于:https://www.cnblogs.com/Miracevin/p/9828971.html
