题解 CF1037D 【Valid BFS?】

· · 题解

我好菜啊qwq

我在赛场上想到了一个奇怪的方法，然后巧妙而又完美地避开了简单的正解qwq

题目意思就不赘述了，我当时非常naive地认为只要后面的深度 \ge 前面的深度。

然后就很愉快地WA了qwq42386330

接着，我茅塞顿开，发现自己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）。

我又开心地发现，我的lower_bound假掉了，因为我没按子节点排序。qwq

然后，我又开心地改掉了，然后开心地交了上去，又WA掉了（42396238）。

我又开心地发现，如果堆了一些叶子节点的vector，size就是0，而我后面在对一个空vector在lower_bound，所以就WA了。qwq

然后就好了。

代码：（42398197）

#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;
}

这题细节好多啊（或许是我写的作死吧）。