# G2. Passable Paths (hard version)

link : https://codeforces.com/problemset/problem/1702/G2

tóm tắt đề : cho 1 cây, có q truy vấn, mỗi truy vấn cho 1 tập đỉnh và hỏi xem tập đó có tạo thành 1 đường đi đơn hay không.

+ suy nghĩ 1: nếu không tạo đường đi đơn thì rẽ nhánh, cần nghĩ điều kiện rẽ nhánh
+ suy nghĩ 2 : có thể add từ từ các node vào xem node vừa add có vi phạm quy tắc hay không

nhận xét : cách làm dài và if else nhiều

:::spoiler

#include<bits/stdc++.h>
#define pii pair<int, int>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)
#define X first
#define Y second

using namespace std;
const int mxn = 2e5 + 5;
int st[mxn], ed[mxn];
int par[18][mxn];
int lan, n, head, l, r;
vector<int> adj[mxn];

void dfs(int u, int p)
{
    st[u] = ++lan;
    par[0][u] = p;
    rep(i, 1, 17) par[i][u] = par[i - 1][par[i - 1][u]];

    for (int v : adj[u]) if (v != p)
        dfs(v, u);
    ed[u] = ++lan;
}

bool is_par(int u, int v)
{
    return (st[u] <= st[v] && ed[u] >= ed[v]);
}

int lca(int u, int v)
{
    if (is_par(u, v)) return u;
    if (is_par(v, u)) return v;

    rev(i, 17, 0) if (!is_par(par[i][u], v))
        u = par[i][u];

    return par[0][u];
}

bool add(int u)
{
    if (u == head) return 1;
    if (head == 0)
    {
        head = u;
        return 1;
    }

    if (l == 0 && r == 0)
    {
        if (is_par(u, head))
        {
            l = head;
            head = u;
            return 1;
        }
        else if (is_par(head, u))
        {
            l = u;
            return 1;
        }
        else
        {
            l = head;
            r = u;
            head = lca(l, r);
            return 1;
        }
    }
    else if (l != 0 && r == 0)
    {
        if (is_par(u, head))
        {
            head = u;
            return 1;
        }
        else if (!is_par(head, u))
        {
            r = u;
            head = lca(u, head);
            return 1;
        }
        else
        {
            if (is_par(u, l)) return 1;
            if (is_par(l, u))
            {
                l = u;
                return 1;
            }

            if (lca(u, l) == head)
            {
                r = u;
                return 1;
            }

            return 0;
        }
    }
    else
    {
        if (is_par(u, head)) return 0;
        else if (!is_par(head, u)) return 0;
        else
        {
            if (is_par(u, l)) return 1;
            if (is_par(l, u))
            {
                l = u;
                return 1;
            }

            if (is_par(u, r)) return 1;
            if (is_par(r, u))
            {
                r = u;
                return 1;
            }
            return 0;
        }
    }
}

int main() {
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);
    cin >> n;
    rep(i, 1, n - 1)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);
    st[0] = -1;
    ed[0] = ++lan;

    int q; cin >> q;
    rep(i, 1, q)
    {
        head = l = r = 0;
        int k; cin >> k;
        bool flag = 1;
        rep(i, 1, k)
        {
            int u; cin >> u;
            if (!flag) continue;
            flag = add(u);
        }

        if (flag) cout << "YES\n";
        else cout << "NO\n";
    }
}

:::

ngoài lề : sol trên cf nghe đơn giản phết, tự thấy mình non=)))))