QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666046#8551. DFS Order 5WedonotLikeStudying#WA 23ms7752kbC++203.2kb2024-10-22 16:24:532024-10-22 16:24:59

Judging History

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

  • [2024-10-22 16:24:59]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:7752kb
  • [2024-10-22 16:24:53]
  • 提交

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;
			else t1[x]=0;
		}
		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();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5712kb

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'