2022/7/14 每日一题(简单路径与树结合---＞深搜)

G1. Passable Paths (easy version) 难度：1900 题意：在一棵树中，每次给出一个询问，再给定一个集合，是否存在一条简单路径经过集合内所有的点。 思路：刚看到这题第一反应是不会做，简单路径的算法看到过，但没有学。 转念一想，简单路径大多应用在图当中，本题要找到一条路径经过集合中所有点，深搜是否就可以做到？况且本题是简单版本，询问最多5次。因此可有下列做法： 1.在构造完一棵树后，预处理出从每个点开始的最大深度。 2.每次询问，对集合内的点进行标记，选出深度最大的点，进行深搜。 3.当对该点遍历的过程中，若遍历到标记的点，则进行加一，若遍历到的点数值等于集合内点数，则进行返回，输出YES。

代码：

#include

using namespace std;
const int N=1e6+5;
int n,p[N],k,h[N];
vectora[N];
mapmp;
bool flag;
void dfs(int x,int pre)
{
    p[x]=p[pre]+1;
    int g=a[x].size();
    for(int i=0;i>n;
    for(int i=1;i>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    int q;cin>>q;
    while(q--)
    {
        mp.clear();
        flag=0;
        cin>>k;
        for(int i=1;i>h[i],mp[h[i]]=1;
        sort(h+1,h+k+1,cmp);
        dfs1(h[1],0,1);
        if(flag)
            cout