QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#672654#8551. DFS Order 5libantian#RE 0ms3484kbC++233.4kb2024-10-24 17:59:062024-10-24 17:59:06

Judging History

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

  • [2024-10-24 17:59:06]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3484kb
  • [2024-10-24 17:59:06]
  • 提交

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

result: