题目链接
题意：给定一棵n个节点的树，和q个询问，每个询问给定包含k个节点的集合，问该集合是否为一条树上的简单路径。（n<2e5）
考的时候没看完题目，这题是一道裸的LCA。
先找到一个深度最深的点u1，再去找另一个不在u1到根路径上的深度最深的点u2，不存在u2就一定是简单路径。
否则对于集合内的其他点判断和u1 u2的距离之和是否就等于u1 与 u2之间的距离。相等就是在路径上。
求LCA用的树剖板子。
#include <bits/stdc++.h>
using namespace std;
namespace IO{
#define I inline
I char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
I void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}
// I void read(int &x){scanf("%d",&x);}
#undef I
}using namespace IO;
const int N = 2e5+5;
int n,m,root,P,a[N];
//有对答案的模数，如果没有需要删去
class TreeChainSubdivision{
#define N 200005
typedef long long LL;
private:
int P;
int head[N],nxt[N<<1],to[N<<1],Cnt;
int dep[N],fa[N],siz[N],hvson[N];
int id[N],idcnt,na[N],top[N];
LL Seg[N<<2],lazy[N<<2];
void update(int Node){Seg[Node]=(Seg[Node<<1]+Seg[Node<<1|1])%P;}
void PushDown(int Node,int L,int R){
if(!lazy[Node])return ;
(lazy[Node<<1]+=lazy[Node])%=P;
(lazy[Node<<1|1]+=lazy[Node])%=P;
(Seg[Node<<1]+=lazy[Node]*L%P)%=P;
(Seg[Node<<1|1]+=lazy[Node]*R%P)%=P;
lazy[Node]=0;
}
void Build(int Node,int L,int R){
if(L==R)return (void)(Seg[Node]=na[L]%P);
int Mid=L+R>>1;
Build(Node<<1,L,Mid);
Build(Node<<1|1,Mid+1,R);
update(Node);
return ;
}
LL QuerySection(int Node,int L,int R,int Ql,int Qr){
if(L>R)return 0;
if(Ql<=L&&R<=Qr)return Seg[Node];
int Mid=L+R>>1;
long long res=0;
PushDown(Node,Mid-L+1,R-Mid);
if(Mid>=Ql)(res+=QuerySection(Node<<1,L,Mid,Ql,Qr))%=P;
if(Mid< Qr)(res+=QuerySection(Node<<1|1,Mid+1,R,Ql,Qr))%=P;
update(Node);
return res;
}
void ModifySection(int Node,int L,int R,int Ml,int Mr,int v){
if(L>R)return ;
if(Ml<=L&&R<=Mr){
(lazy[Node]+=v)%=P;
(Seg[Node]+=1ll*v*(R-L+1)%P)%=P;
return ;
}
int Mid=L+R>>1;
PushDown(Node,Mid-L+1,R-Mid);
if(Mid>=Ml)ModifySection(Node<<1,L,Mid,Ml,Mr,v);
if(Mid< Mr)ModifySection(Node<<1|1,Mid+1,R,Ml,Mr,v);
update(Node);
return ;
}
void dfs1(int x,int f,int deep){//处理出每个节点的深度、父节点、子树大小和重儿子
dep[x]=deep,fa[x]=f,siz[x]=1;
int mxsiz=0;
for(int i=head[x];~i;i=nxt[i])if(to[i]^f){
dfs1(to[i],x,deep+1);
siz[x]+=siz[to[i]];
if(mxsiz<siz[to[i]])mxsiz=siz[to[i]],hvson[x]=to[i];
}
}
void dfs2(int x,int Ltop){//按dfs序标号、处理每条链,Ltop表示链的顶端
id[x]=++idcnt;
na[idcnt]=a[x];
top[x]=Ltop;
if(!hvson[x])return ;
dfs2(hvson[x],Ltop);
for(int i=head[x];~i;i=nxt[i])if(to[i]^hvson[x]&&to[i]^fa[x]){
dfs2(to[i],to[i]);
}
}
public:
int a[N];
void init(int _n,int _root,int _P){
n=_n,root=_root,P=_P;
Cnt=idcnt=0;
memset(head,-1,sizeof(head));
}
int Dep(int x){return dep[x];}
void AddEdge(int u,int v){
nxt[Cnt]=head[u],to[Cnt]=v,head[u]=Cnt++;
}
void Solve(void){
dfs1(root,0,1),dfs2(root,root);
}
int LCA(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]>dep[y]?y:x;
}
LL QueryRoute(int x,int y){
LL res=0;
while(top[x]^top[y]){//x、y不在一条链上
if(dep[top[x]]<dep[top[y]])swap(x,y);//让x所在链作为深度更深的点
(res+=QuerySection(1,1,n,id[top[x]],id[x]))%=P;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
(res+=QuerySection(1,1,n,id[x],id[y]))%=P;
return res;
}
void ModifyRoute(int x,int y,int c){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ModifySection(1,1,n,id[top[x]],id[x],c);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ModifySection(1,1,n,id[x],id[y],c);
}
LL QuerySubtree(int x){
return QuerySection(1,1,n,id[x],id[x]+siz[x]-1);
}
void ModifySubtree(int x,int c){
return (void)(ModifySection(1,1,n,id[x],id[x]+siz[x]-1,c));
}
int GetDis(int x,int y){
return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
#undef N
}T;
int Q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n);
T.init(n,1,P);
for(int i=1,x,y;i<n;++i){
read(x),read(y);
T.AddEdge(x,y),T.AddEdge(y,x);
}
T.Solve();
for(read(Q);Q;--Q){
int k;read(k);
for(int i=1;i<=k;++i)read(a[i]);
int u1=0,u2=0;
for(int i=1;i<=k;++i)if(T.Dep(a[i])>T.Dep(u1))u1=a[i];
for(int i=1;i<=k;++i)if(a[i]^u1){
if(T.LCA(u1,a[i])^a[i]){
if(T.Dep(a[i])>T.Dep(u2))u2=a[i];
}
}
if(!u2){
puts("YES");
continue;
}
int rec=T.GetDis(u1,u2),flg=1;
for(int i=1;i<=k;++i)if(a[i]^u1&&a[i]^u2){
if(T.GetDis(u1,a[i])+T.GetDis(a[i],u2)!=rec){
flg=0;
break;
}
}
puts(flg?"YES":"NO");
}
}