ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196860 | #2644. path | tkswls | 100 | 1247ms | 22628kb | C++ | 1.2kb | 2023-11-02 09:58:32 | 2023-11-02 12:04:28 |
answer
#include <bits/stdc++.h>
using namespace std;
int n, m;
int fa[200005][21], ccnt, nxt[400005], head[200005], to[400005], d[400005], a[200005];
inline void add(int p, int q) {
nxt[++ccnt] = head[p];
to[ccnt] = q;
head[p] = ccnt;
}
inline void dfs(int p, int q) {
fa[p][0] = q;
d[p] = d[q] + 1;
for (int i = 1; i <= 20; i++) {
fa[p][i] = fa[fa[p][i - 1]][i - 1];
}
for (int i = head[p]; i; i = nxt[i]) {
if (to[i] != q) {
dfs(to[i], p);
}
}
}
inline bool chefa(int p, int q) {
if (d[p] == d[q]) {
return (p == q);
}
if (d[p] > d[q]) return false;
for (int i = 20; i >= 0; i--) {
if (d[fa[q][i]] >= d[p]) q = fa[q][i];
}
return (p == q);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int p, q;
for (int i = 1; i < n; i++) {
cin >> p >> q;
add(p, q), add(q, p);
}
dfs(1, 0);
for (int i = 1; i <= m; i++) {
cin >> p;
int minn = 0;
for (int j = 1; j <= p; j++) {
cin >> a[j];
if (a[j] != 1) a[j] = fa[a[j]][0];
if (d[minn] < d[a[j]]) minn = a[j];
}
bool ans = true;
for (int j = 1; j <= p; j++) {
ans &= chefa(a[j], minn );
}
if (ans) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 7400kb
input:
4633 5 1 2 1 3 2 4 1 5 2 6 6 7 1 8 2 9 7 10 7 11 3 12 12 13 3 14 2 15 14 16 5 17 15 18 7 19 7 20 19 ...
output:
NO YES YES YES NO
result:
ok 5 lines
Test #2:
score: 5
Accepted
time: 0ms
memory: 7400kb
input:
4940 5 1 2 2 3 3 4 2 5 1 6 1 7 1 8 8 9 6 10 2 11 1 12 2 13 11 14 7 15 14 16 6 17 5 18 17 19 10 20 8 ...
output:
YES YES YES YES NO
result:
ok 5 lines
Test #3:
score: 5
Accepted
time: 0ms
memory: 7400kb
input:
4747 5 1 2 2 3 3 4 2 5 5 6 3 7 2 8 6 9 6 10 10 11 10 12 4 13 6 14 11 15 14 16 7 17 4 18 9 19 15 20 1...
output:
YES YES YES YES YES
result:
ok 5 lines
Test #4:
score: 5
Accepted
time: 0ms
memory: 7392kb
input:
4554 5 1 2 1 3 1 4 2 5 4 6 4 7 2 8 4 9 5 10 5 11 9 12 6 13 1 14 2 15 6 16 8 17 11 18 1 19 18 20 12 2...
output:
YES YES YES YES YES
result:
ok 5 lines
Test #5:
score: 5
Accepted
time: 3ms
memory: 7396kb
input:
4861 5 1 2 1 3 1 4 2 5 3 6 5 7 2 8 2 9 5 10 3 11 7 12 8 13 9 14 6 15 6 16 9 17 10 18 11 19 4 20 1 21...
output:
YES YES NO YES YES
result:
ok 5 lines
Test #6:
score: 5
Accepted
time: 6ms
memory: 7400kb
input:
4736 5000 1 2 2 3 2 4 2 5 1 6 2 7 7 8 8 9 2 10 3 11 9 12 7 13 3 14 5 15 8 16 7 17 8 18 11 19 12 20 4...
output:
YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES YES NO YES YES YES YES YES NO YES YES YES ...
result:
ok 5000 lines
Test #7:
score: 5
Accepted
time: 6ms
memory: 7404kb
input:
4850 5000 1 2 1 3 3 4 2 5 4 6 5 7 1 8 4 9 1 10 6 11 5 12 11 13 6 14 14 15 15 16 9 17 5 18 12 19 1 20...
output:
YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YE...
result:
ok 5000 lines
Test #8:
score: 5
Accepted
time: 3ms
memory: 7400kb
input:
4657 5000 1 2 2 3 1 4 2 5 3 6 6 7 1 8 2 9 1 10 1 11 3 12 1 13 1 14 4 15 15 16 10 17 4 18 4 19 4 20 1...
output:
YES YES NO YES NO NO YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES NO...
result:
ok 5000 lines
Test #9:
score: 5
Accepted
time: 0ms
memory: 7404kb
input:
4771 5000 1 2 1 3 2 4 3 5 4 6 3 7 2 8 6 9 9 10 4 11 11 12 5 13 4 14 13 15 7 16 12 17 1 18 6 19 14 20...
output:
YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YE...
result:
ok 5000 lines
Test #10:
score: 5
Accepted
time: 2ms
memory: 7404kb
input:
4885 5000 1 2 2 3 3 4 3 5 2 6 6 7 3 8 2 9 8 10 7 11 7 12 9 13 7 14 8 15 14 16 14 17 7 18 8 19 3 20 1...
output:
NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES NO NO Y...
result:
ok 5000 lines
Test #11:
score: 5
Accepted
time: 105ms
memory: 22432kb
input:
183099 40000 1 2 1 3 2 4 3 5 1 6 3 7 1 8 1 9 7 10 8 11 2 12 1 13 13 14 10 15 10 16 7 17 12 18 18 19 ...
output:
YES NO YES NO NO YES YES YES NO NO NO NO YES NO YES NO NO YES YES NO YES YES YES YES YES NO YES NO Y...
result:
ok 40000 lines
Test #12:
score: 5
Accepted
time: 104ms
memory: 22628kb
input:
199906 40000 1 2 2 3 3 4 3 5 5 6 5 7 1 8 7 9 7 10 3 11 11 12 3 13 8 14 14 15 2 16 8 17 2 18 10 19 4 ...
output:
NO YES YES NO YES YES NO NO YES NO YES NO NO NO NO NO YES NO YES NO YES YES NO YES NO YES YES NO NO ...
result:
ok 40000 lines
Test #13:
score: 5
Accepted
time: 104ms
memory: 22484kb
input:
196713 40000 1 2 2 3 3 4 3 5 4 6 6 7 1 8 5 9 6 10 1 11 9 12 5 13 3 14 4 15 2 16 9 17 9 18 2 19 7 20 ...
output:
NO YES NO NO YES YES YES YES NO YES NO NO YES YES NO NO NO YES NO NO NO YES NO YES NO YES YES YES NO...
result:
ok 40000 lines
Test #14:
score: 5
Accepted
time: 98ms
memory: 22464kb
input:
190327 40000 1 2 1 3 1 4 4 5 5 6 3 7 2 8 1 9 5 10 4 11 5 12 9 13 6 14 13 15 9 16 11 17 15 18 4 19 15...
output:
NO NO NO YES YES NO NO YES NO YES NO NO YES NO NO NO NO NO NO NO YES NO YES NO NO YES YES NO NO NO N...
result:
ok 40000 lines
Test #15:
score: 5
Accepted
time: 101ms
memory: 22448kb
input:
187134 40000 1 2 2 3 2 4 4 5 4 6 4 7 2 8 7 9 5 10 9 11 3 12 11 13 1 14 4 15 9 16 12 17 14 18 14 19 1...
output:
YES YES YES NO YES NO NO YES YES NO YES YES YES NO YES YES YES NO YES NO NO NO NO YES NO NO YES YES ...
result:
ok 40000 lines
Test #16:
score: 5
Accepted
time: 91ms
memory: 22440kb
input:
183941 40000 1 2 2 3 2 4 4 5 3 6 5 7 3 8 5 9 5 10 7 11 2 12 1 13 9 14 8 15 9 16 13 17 4 18 6 19 4 20...
output:
NO NO YES NO YES NO YES YES NO NO YES YES YES YES YES NO NO NO YES NO YES NO YES YES YES YES YES NO ...
result:
ok 40000 lines
Test #17:
score: 5
Accepted
time: 93ms
memory: 22424kb
input:
180748 40000 1 2 1 3 3 4 4 5 2 6 6 7 3 8 3 9 4 10 5 11 11 12 3 13 4 14 13 15 1 16 14 17 11 18 16 19 ...
output:
NO NO YES YES NO YES NO YES NO YES NO NO YES YES YES NO NO YES NO YES YES YES YES NO NO YES NO YES Y...
result:
ok 40000 lines
Test #18:
score: 5
Accepted
time: 182ms
memory: 22480kb
input:
194362 40000 1 2 2 3 1 4 1 5 5 6 3 7 4 8 7 9 3 10 8 11 7 12 7 13 7 14 8 15 1 16 16 17 17 18 18 19 17...
output:
YES YES YES NO YES YES YES NO YES YES YES NO YES NO YES YES YES NO YES NO YES NO NO YES YES NO YES N...
result:
ok 40000 lines
Test #19:
score: 5
Accepted
time: 171ms
memory: 22464kb
input:
191169 40000 1 2 2 3 1 4 1 5 4 6 4 7 4 8 5 9 3 10 3 11 5 12 9 13 2 14 12 15 8 16 1 17 16 18 10 19 3 ...
output:
NO YES YES YES NO NO NO NO NO NO YES YES NO YES YES YES NO NO NO YES YES NO YES YES YES NO YES YES N...
result:
ok 40000 lines
Test #20:
score: 5
Accepted
time: 178ms
memory: 22456kb
input:
187976 40000 1 2 2 3 2 4 1 5 3 6 6 7 4 8 2 9 3 10 1 11 3 12 11 13 10 14 3 15 8 16 2 17 6 18 2 19 6 2...
output:
NO YES YES NO YES YES YES NO YES YES YES YES YES YES NO YES YES NO NO NO NO NO YES NO YES YES YES NO...
result:
ok 40000 lines