Question

[Ngu tin]

Giúp với

Answer 1

[Anh Phạm]

#include <bits/stdc++.h>
#define forvct(i,v) for(int i = 0, _key = v.size(); i < _key; ++i)
#define forinc(i,a,b) for(int i = a, _key = b; i <= _key; ++i)
#define fordec(i,a,b) for(int i = a, _key = b; i >= _key; --i)
#define p_b push_back
#define ll long long
#define nn 100001

using namespace std;

int n, m, l, q, t, res, test,
    a[nn], tin[nn], tout[nn], mark[nn], terror[nn], p[nn][20];
vector<int> adj[nn], _adj[nn];
stack<int> stk;

void enter()
{
    cin >> n;
    int u, v;
    forinc(i,1,n-1)
    {
        cin >> u >> v;
        adj[u].p_b(v);
        adj[v].p_b(u);
    }
    l = log2(n);
    cin >> q;
}

void visit(const int &u)
{
    tin[u] = ++t;
    forinc(j,1,l) p[u][j] = p[p[u][j-1]][j-1];
    forvct(j,adj[u])
    {
        int v = adj[u][j];
        if (v != p[u][0])
        {
            p[v][0] = u;
            visit(v);
        }
    }
    tout[u] = ++t;
}

bool anc(const int &u, const int &v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (anc(u,v)) return u;
    if (anc(v,u)) return v;
    fordec(j,l,0)
        if (!anc(p[u][j],v)) u = p[u][j];
    return p[u][0];
}

bool cmp(const int &x, const int &y)
{
    return tin[x] < tin[y];
}

bool check(const int &u)
{
    int cnt = 0;
    forvct(j,_adj[u])
    {
        int v = _adj[u][j];
        if (terror[u] == test)
        {
            if (terror[v] == test && p[v][0] == u)
            {
                res = -1;
                return -1;
            }
            bool x = check(v);
            if (res == -1) return -1;
            res += x;
        }
        else
        {
            bool x = check(v);
            if (res == -1) return -1;
            cnt += x;
        }
    }
    if (terror[u] == test || cnt == 1) return 1;
    if (cnt > 1) res++;
    return 0;
}

void query()
{
    cin >> m;
    forinc(i,1,m)
    {
        cin >> a[i];
        _adj[a[i]].clear();
        mark[a[i]] = test;
        terror[a[i]] = test;
    }
    sort(a+1,a+m+1,cmp);
    forinc(i,1,m-1)
    {
        int tmp = lca(a[i],a[i+1]);
        if (mark[tmp] < test)
        {
            mark[tmp] = test;
            a[++m] = tmp;
            _adj[tmp].clear();
        }
    }
    sort(a+1,a+m+1,cmp);
    while (!stk.empty()) stk.pop();
    stk.push(a[1]);
    forinc(i,2,m)
    {
        while (tout[stk.top()] < tout[a[i]]) stk.pop();
        _adj[stk.top()].p_b(a[i]);
        stk.push(a[i]);
    }
    res = 0;
    check(a[1]);
    cout << res << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    enter();
    p[1][0] = 1;
    visit(1);
    for(test = 1; test <= q; ++test) query();
}