QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672685 | #8548. China Convex Polygon Contest | libantian# | RE | 0ms | 0kb | C++23 | 3.6kb | 2024-10-24 18:07:50 | 2024-10-24 18:07:50 |
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);
set<int> s;
for(int i=1;i<=k;i++){
cin>>a[i];
s.insert(a[i]);
}
if(s.size()!=k){
cout<<"No"<<endl;
continue;
}
// 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(mp.empty()||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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 3 10 1 5 9 1 2 3 3 10 1 5 9 1 1 4 3 10 1 5 9 1 5 10