Codeforces Round #629 (Div. 3) E.Tree Queries (DFS)
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS)
作者：HeHao何浩
思路：若ai 在路径上 ，则ai的父结点一定在路径上，若ai是路径上某个结点的子结点，则ai的父结点一定在路径上，综上只需考虑ai的父节点就行了。对每个ai判断一下ai-1是否能到达ai,若存一个不行则输出NO，反之输出YES.
用f[i]存储父结点，用dfs[i]记录访问顺序，用sz[i]保存 子树结点数。详情见代码
#include
using namespace std;
const int N=2e5+5;
int n,m,h[N],sz[N],dfn[N],cnt,f[N],num,a[N];//sz[i]储存结点以结点i为根的子树的结点数,f[i]储存i的父结点.
struct edge{//边
int to,nt;
}e[N<<1];
void add(int u,int v){//链式前向星。
cnt++;
e[cnt].to=v;
e[cnt].nt=h[u];
h[u]=cnt;
}
void dfs(int u,int fa){ //dfs
f[u]=fa;
dfn[u]=++num;//储存访问顺序
sz[u]=1;//初始化
for(int i=h[u];i;i=e[i].nt)
{
int v=e[i].to;
if(v!=fa){
dfs(v,u);
sz[u]+=sz[v];
}
}
}
bool cmp(int a,int b){ //按访问顺序排序
return dfn[a]>n>>m;
ios::sync_with_stdio(false),cin.tie(0);
for(int i=1,u,v;i>u>>v;
add(u,v),add(v,u);
}
dfs(1,0);
while(m--){
int k;
cin>>k;
for(int i=1;i>a[i];
if(a[i]!=1) a[i]=f[a[i]];//特判 因为1没有父结点
}
sort(a+1,a+k+1,cmp);
int ok=1;
for(int i=2;i<=k;i++)
if(dfn[a[i-1]]+sz[a[i-1]]-1<dfn[a[i]]) //若a[i-1]到达不了a[i]
{
ok=0;
break;
}
puts(ok?"YES":"NO");
}
return 0;
}
作者：HeHao何浩
