//有效的BFS Valid BFS | CF1037D #include #include #include #include #include #include using namespace std; bool visited[200001]; vector G[200001]; //图的邻接表 int main() { int temp, tempFrom, tempTo, n, currPos, childNum; vector::iterator it; queue reqSeq, visitSeq; //请求访问顺序,实际访问顺序 set childSet; scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d %d", &tempFrom, &tempTo); G[tempFrom].push_back(tempTo); G[tempTo].push_back(tempFrom); } for (int i = 0; i < n; i++) { scanf("%d", &temp); reqSeq.emplace(temp); } visitSeq.push(1); reqSeq.pop(); while (!visitSeq.empty()) { currPos = visitSeq.front(); visitSeq.pop(); if (visited[currPos]) { continue; } visited[currPos] = true; for (it = G[currPos].begin(); it != G[currPos].end(); it++) { if (!visited[*it]) { childSet.emplace(*it); } } childNum = childSet.size(); for (int i = 0; i < childNum; i++) { set::iterator it = childSet.find(reqSeq.front()); if (it == childSet.end()) { printf("No"); return 0; } visitSeq.emplace(reqSeq.front()); reqSeq.pop(); } childSet.clear(); //清空儿子集合 } printf("Yes"); return 0; }