结题报告--hih0CoderP1041

题目：

                                      描述

小hi和小ho准备国庆期间去a国旅游。a国的城际交通比较有特色：它共有n座城市(编号1-n)；城市之间恰好有n-1条公路相连，形成一个树形公路网。小hi计划从a国首都(1号城市)出发，自驾遍历所有城市，并且经过每一条公路恰好两次——来回各一次——这样公路两旁的景色都不会错过。

 

令小hi苦恼的是他的小伙伴小ho希望能以某种特定的顺序游历其中m个城市。例如按3-2-5的顺序游历这3座城市。(具体来讲是要求：第一次到达3号城市比第一次到达2号城市早，并且第一次到达2号城市比第一次到达5号城市早)。

 

小hi想知道是否有一种自驾顺序满足小ho的要求。

                                     思路

这里使用dfs序列。以一下树为例：

（图片来源于百度，所以后面又‘#’，懒得删了）

dfs序列：abdce。

为方便理解算法，我们把结点写两遍，变成：abddbceeca。

假如小ho的要求序列是adc，那么是可行的，那在dfs序列里怎么判断呢？

答：小ho要求的顶点序列每一个点前面的所有顶点都不在两个此节点中间。

根据这个答案，写出的代码wa0分，样例也过不去，输出全是yes，而应该是yes和no。

分析一下错误答案。

树：

（原谅我丑陋无比的图）

dfs序：1244552366771

分析一下：3不在两个二之间，3和2都不在两个7之间，所以程序认为它是可以的，可是因为3和7之间夹着一个2，所以不可以。因此，得出结论：不仅要前面的算法，还需要保证一个节点后要么没有子孙节点，有则必须是连续的。

最后，结合粗体字，就是ac代码了

对付多数据的mains发点此

                       犯的错误

1.数组没初始化（每次都要重新初始化，因为每次都是一棵新的树）

2.重命名了（那个dfsx数组，猜我为啥加个x？）

3.cnt不用每次访问完就++，++一次就行了

4.思路中的第二点我开始没考虑到

5.判断第二个条件时，i和j的初值错了

6.为了调试方便，可以用set（将所有子节点放入set再查找，复杂度o(n),好于两重循环。）

                        收获

1.再重复那几个字：初始化，初始化，初始化（重要的事情说三遍！！）

2.以后所有名称尽量不要叫“dfs”，因为dfs有：函数、栈、数组（dfs序……），叫“dfs”很容易重命名，同理，bfs也不行。

3.做题时，所有的方面可能开始没考虑到，可是之后一定到考虑到。

4.stl不要省着用！（若想判断你是否省着用stl，看看这题你是否想到了用stl的解法）