Codeforces Round #629 (Div. 3) E - Tree Queries

問題概要

• 問題へのリンク

木が与えられる。 各クエリに答えよ。

• クエリ

個の頂点が与えられる。これらの頂点すべてからの距離が1以下となるパスが存在するか答えよ。

解説

最も深い頂点と、その前の頂点のLCAを求めて、そことの距離が1より大きいものがあればNo。

実装

提出へのリンク

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int N, Q;
    cin >> N >> Q;
    LCA<long long> G(N);
    G.input(N-1, -1, false, false);
    G.dfs();
    while(Q--){
        int K;
        cin >> K; 
        vec<int> v(K);
        rep(i,K){
            cin >> v[i];
            v[i]--;
        }
        int maxx = -1;
        int mx_idx = -1;
        rep(i,K){
            if(chmax(maxx, G.d[v[i]])){
                mx_idx = v[i];
            }
        }
        bool ok = true;
        rep(i,K){
            int lca = G.lca(mx_idx, v[i]);
            int dist = G.calc_dist(v[i],lca);
            if(dist > 1)ok = false;
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
}