QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672654 | #8551. DFS Order 5 | libantian# | RE | 0ms | 3484kb | C++23 | 3.4kb | 2024-10-24 17:59:06 | 2024-10-24 17:59:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
struct HLD {
int n, idx;
vector<vector<int>> ver;
vector<int> siz, dep,cnt;
vector<int> top, son, parent;
HLD(int n) {
this->n = n;
ver.resize(n + 1);
siz.resize(n + 1);
dep.resize(n + 1);
cnt.resize(n + 1);
top.resize(n + 1);
son.resize(n + 1);
parent.resize(n + 1);
}
void add(int x, int y) { // 建立双向边
ver[x].push_back(y);
ver[y].push_back(x);
}
void dfs1(int x) {
siz[x] = 1;
dep[x] = dep[parent[x]] + 1;
for (auto y : ver[x]) {
if (y == parent[x]) continue;
cnt[x]++;
parent[y] = x;
dfs1(y);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) {
son[x] = y;
}
}
}
void dfs2(int x, int up) {
top[x] = up;
if (son[x]) dfs2(son[x], up);
for (auto y : ver[x]) {
if (y == parent[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
x = parent[top[x]];
} else {
y = parent[top[y]];
}
}
return dep[x] < dep[y] ? x : y;
}
int clac(int x, int y) { // 查询两点间距离
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
void work(int root = 1) { // 在此初始化
dfs1(root);
dfs2(root, root);
}
};
void solve(){
int n,q;
cin>>n>>q;
HLD hld(n);
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
hld.add(x,y);
}
hld.work();
while(q--){
int k;
cin>>k;
vector<int>a(k+1);
for(int i=1;i<=k;i++)cin>>a[i];
// for(int i=1;i<=k;i++)cout<<a[i]<<" ";
// cout<<endl;
if(k==1){
cout<<"Yes"<<endl;
continue;
}
int p=a[1];
for(int i=2;i<=k;i++)p=hld.lca(p,a[i]);
map<int,int>mp;
//cout<<p<<endl;
if(p==a[1]){
mp[hld.dep[p]]=hld.cnt[p];
}else{
if(hld.cnt[p]-1)mp[hld.dep[p]]=hld.cnt[p]-1;
if(hld.cnt[a[1]])mp[hld.dep[a[1]]]=hld.cnt[a[1]];
}
//for(auto v:mp)cout<<v.fi<<" "<<v.se<<endl;
// for(int i=1;i<=k;i++)cout<<a[i]<<" ";
// cout<<endl;
bool is=true;
for(int i=2;i<=k;i++){
// cout<<i<<" "<<a[k]<<endl;
int d=hld.dep[hld.parent[a[i]]];
//cout<<d<<endl;
if(d!=(*mp.rbegin()).fi){
//cout<<i<<endl;
is=false;
break;
}else{
mp[d]--;
if(mp[d]==0)mp.erase(d);
}
if(hld.cnt[a[i]])mp[hld.dep[a[i]]]+=hld.cnt[a[i]];
}
if(is)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << setiosflags(ios::fixed) << setprecision(15);
int T;
T=1;
//cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3484kb
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
Runtime Error
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