QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#666019#8551. DFS Order 5WedonotLikeStudying#WA 23ms7680kbC++203.6kb2024-10-22 16:18:372024-10-22 16:18:39

Judging History

你现在查看的是最新测评结果

  • [2024-10-22 16:18:39]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:7680kb
  • [2024-10-22 16:18:37]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define db long double
#define ll long long
#define vi vector<int>
#define pb emplace_back
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

template<class T>inline void read(T &x) {
	T f=1; x=0; char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}

const int N=1e5;
const int inf=0x3f3f3f3f;

int n,Q,qx[N+5];

vi e[N+5];

int dep[N+5],fa[N+5],siz[N+5],son[N+5],top[N+5],dfn[N+5],vs[N+5],tg[N+5],al[N+5],nd[N+5],sz,t1[N+5],t2[N+5],ss[N+5];

inline void dfs1(int x) {
	siz[x]=1;
	for(int v:e[x]) if(v!=fa[x]) {
		fa[v]=x;
		dep[v]=dep[x]+1;
		dfs1(v);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]]) son[x]=v;
	}
}

inline void dfs2(int x,int topf) {
	top[x]=topf; dfn[x]=(++dfn[0]);
	if(son[x]) dfs2(son[x],topf);
	for(int v:e[x]) if(v!=fa[x]&&v!=son[x]) dfs2(v,v);
}

inline 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]?x:y;
}

int val[N+5];
inline int lo(int x) { return (x&(-x)); }
inline void upd(int x,int ch) { while(x<=n) val[x]+=ch,x+=lo(x); }
inline int qry(int x) { int ans=0; while(x) ans+=val[x],x-=lo(x); return ans; }

inline int chk(int Fa,int x) { return (dfn[x]>=dfn[Fa])&&((dfn[Fa]+siz[Fa]-1)>=dfn[x]); }

inline void solve() {
	read(n); read(Q);
	rep(i,1,n-1) {
		int u,v;
		read(u); read(v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs1(1); dfs2(1,1);
	rep(i,1,n) ss[i]=e[i].size()-1;
	ss[1]++;
	rep(asd_a,1,Q) {
		int k,Tag=0;
		read(k);
		rep(i,1,k) read(qx[i]);
		rep(i,1,k) tg[qx[i]]=0,t1[qx[i]]=0,t2[qx[i]]=0;
		rep(i,1,k) tg[qx[i]]++;
		rep(i,1,k) if(tg[qx[i]]>1) {
			Tag=1;
			break;
		}
		rep(i,1,k) {
			int x=qx[i];
			int Sz=qry(dfn[x]+siz[x]-1)-qry(dfn[x]-1);
			upd(dfn[x],1);
			if(Sz) Tag=1;
		}
		rep(i,1,k) upd(dfn[qx[i]],-1);
		if(Tag) {
			puts("No");
			continue;
		}
		per(i,k,1) {
			int x=qx[i];
			upd(dfn[x],1);
			int Sz=qry(dfn[x]+siz[x]-1)-qry(dfn[x]-1);
			if(Sz==siz[x]) t1[x]=1;
		}
		rep(i,1,k) upd(dfn[qx[i]],-1),t2[qx[i]]=0;
		per(i,k,1) {
			int x=qx[i],pos=i+1;
			if(!t1[x]) continue;
			if(siz[x]==1) {
				t2[x]=1;
				continue;
			}
			t2[x]=1;
			rep(j,1,ss[x]) {
				if(fa[qx[pos]]!=x) {
					t2[x]=0;
					break;
				}
				if(!t2[qx[pos]]) {
					t2[x]=0;
					break;
				}
				pos+=siz[qx[pos]];
			}
		}
		rep(i,1,k) if(t1[qx[i]]!=t2[qx[i]]) {
			Tag=1;
			break;
		}
		if(Tag) {
			puts("No");
			continue;
		}
		sz=0;
		for(int i=1;i<=k;) {
			nd[++sz]=qx[i];
			if(!t1[qx[i]]) break;
			i+=siz[qx[i]];
		}
		int lca=nd[1];
		rep(i,2,sz) {
			int Lca=LCA(lca,nd[i]);
			if(chk(lca,nd[i])) Tag=1;
			else if(fa[nd[i]]!=Lca) Tag=1;
			lca=Lca;
		}
		if(Tag) {
			puts("No");
			continue;
		}
		int pos=1,Pos=nd[sz];
		rep(i,1,k) if(qx[i]==nd[sz]) pos=i+1;
		for(;pos<=k;) {
			if(fa[qx[pos]]!=Pos) {
				Tag=1;
				break;
			}
			if(t2[qx[pos]]) pos+=siz[qx[pos]];
			else Pos=qx[pos],pos++;
		}
		if(Tag) puts("No");
		else puts("Yes");
	}
}

int main() {
	//int T; read(T); while(T--)
	solve();
}
/*
6 8
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5
3 5 2 4

10 2
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7680kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
No
Yes
Yes

result:

ok 7 tokens

Test #2:

score: -100
Wrong Answer
time: 23ms
memory: 5716kb

input:

10 100000
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
9 4 2 3 10 2 5 4 3 ...

output:

No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

wrong answer 1919th words differ - expected: 'Yes', found: 'No'