题解 CF1037D 【Valid BFS?】

我好菜啊qwq 我在赛场上想到了一个奇怪的方法，然后巧妙而又完美地避开了简单的正解qwq 题目意思就不赘述了，我当时非常$naive$地认为只要后面的深度$ \ge $前面的深度。 然后就很愉快地$WA$了qwq[42386330](http://codeforces.com/contest/1037/submission/42386330) 接着，我茅塞顿开，发现自己$naive$了。 看着代码，因为我写了个$dfs$求深度和父节点，然后我又不舍得删掉，进行了一番分析后发现了一个玄妙的方法： （敲黑板）我发现自己的代码之所以$WA$了，是因为一种长成这样的形态：  此时，虽然满足后面深度$ \ge $前面深度，但由于$2$的子节点在$3$的前面，所以$5$在$4$前是不合法的（$naive$ qwq）。 对着这个错误的，假的代码，我想出了这么个东西： 因为先访问的节点的子节点（直系子节点，以后亦是这个意思）也是先访问的，所以这个好像也是个队列。 所以，我们可以开一个队列，来模拟这个事情。有人就说，搞什么啊，不又回到基本的$BFS$了吗？但是，这个题目的特别就在于每一个节点的子节点是按随机的顺序加入到队列，但这个顺序又决定了这些节点子节点的顺序，所以说我对于一个节点的每个儿子是不能区分的，而只能在儿子的儿子把每一个儿子的所有儿子相对区分出来（好像有点抽象啊）。 举个例子，  在这个图中，如果$1$先入了队，那我们不能在搜索它的子节点时把$2$放在$3$的前面，否则就不符合题意了。所以我们怎么排$2$和$3$继续往后搜呢？ 很简单，我们边做边判断。 在此时，入队的一定是$2$或$3$，所以我们读入下一个入队的，判断一下，自然就知道先访问的哪个节点了。比如$BFS$序中下一个是$3$，那我们就把$3$的子节点丢到队尾就行了。后面又来了个$2$，我们就把$2$的子节点丢到队尾，然后就可以区分相对顺序。 但怎么把不同节点的新一层子节点区分出来呢？还要写一大堆的东西保留分界线吗？ 我当时脑子一抽，想到了个玩意儿，叫$queue<vector<int>>$。qwq 把每个节点的子节点预处理出来，存在一个$vector$数组$son$里，然后先判一下$1$，若合法则将$son[1]$插到$q$里。 然后当我们要判有没有$x$时，只要在$q.front()$里$lower_bound()$一下（因为我太弱了，写不好$vector$的二分函数），判断是不是$x$，不是就$-1$，否则就删掉。 但删掉的复杂度是不对的，因为$vector$的删除是线性的。接着，我脑子又一抽，问了一个问题：  所以说询问的不重复，而$vector$也不重复，所以说一个点只会被出队（$vector$）一次。 那还要删除干嘛，直接搞个计数器累加一下看看等不等于$size$不就行了吗。 然后，我开心地写完了，然后开心地交了上去，$WA$掉了（[42393717](http://codeforces.com/contest/1037/submission/42393717)）。 我又开心地发现，我的$lower_bound$假掉了，因为我没按子节点排序。qwq 然后，我又开心地改掉了，然后开心地交了上去，又$WA$掉了（[42396238](http://codeforces.com/contest/1037/submission/42396238)）。 我又开心地发现，如果堆了一些叶子节点的$vector$，$size$就是$0$，而我后面在对一个空$vector$在$lower_bound$，所以就$WA$了。qwq 然后就好了。 代码：（[42398197](http://codeforces.com/contest/1037/submission/42398197)） ```cpp #pragma comment (linker,"/STACK:1024000000") #pragma GCC optimize(2) #pragma GCC target(arch=corie7-acx) #include<bits/stdc++.h> using namespace std; int n; vector<int> E[200001]; vector<int> son[200001]; int fa[200001]; void dfs (int u) { for (auto v:E[u]) { if (v==fa[u]) continue; son[u].push_back(v); fa[v]=u; dfs(v); } return; } int u,v; int x,m; queue<vector<int>> q; vector<int> t; int num,sum; vector<int>::iterator it; int main() { scanf("%d",&n); for (int i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); E[u].push_back(v); E[v].push_back(u); } dfs(1); scanf("%d",&x); if (x!=1) return puts("No"),0; q.push(son[1]); t=q.front(); sort(t.begin(),t.end()); for (int i=2;i<=n;i++) { scanf("%d",&x); while (sum==t.size()) { q.pop(); if (q.empty()) return puts("No"),0; t=q.front(); sort(t.begin(),t.end()); sum=0; } it=(lower_bound(t.begin(),t.end(),x)+1); //printf("%d ",x); num=it-t.begin(); //printf("%d:%d\n",num,t[num-1]); if (x!=t[num-1]) return puts("No"),0; sum++; q.push(son[x]); } printf("Yes"); return 0; } ``` 这题细节好多啊（或许是我写的作死吧）。