Submission #1093038

#TimeUsernameProblemLanguageResultExecution timeMemory
1093038MrPavlitoRailway (BOI17_railway)C++17
36 / 100
64 ms32140 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
///#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
const int lg = 18;

int up[MAXN][lg];
int dist[MAXN];
int tin[MAXN];
int tout[MAXN];
int cnt[MAXN];
int t = 1;
int n,m,k;
vector<vector<int>> graf(MAXN);


void dfs(int nod, int p, int d)
{
    dist[nod] = d;
    up[nod][0] = p;
    tin[nod] = t++;
    for(auto x: graf[nod])if(x!=p)dfs(x,nod,d+1);
    tout[nod] = t++;
}

void fillUp()
{
    for(int i=1; i<lg; i++)
    {
        for(int j=1; j<=n; j++)
        {
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
}

int lca(int u,int v)
{
    if(u == v)return u;
    if(tin[u] < tin[v] && tout[u] > tout[v])return u;
    if(tin[u] > tin[v] && tout[u] < tout[v])return v;

    for(int i=lg-1; i>=0; i--)
    {
        int probaj = up[v][i];
        if(!(tin[probaj] < tin[u] && tout[probaj] > tout[u]))v = probaj;
    }
    return up[v][0];
}

int dfs2(int nod, int p)
{
    for(auto x:graf[nod])
    {
        if(x==p)continue;
        cnt[nod] += dfs2(x,nod);
    }
    return cnt[nod];
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {

        cin >> n >> m>> k;
        vector<pii>svi_putevi(n-1);
        for(int i=0; i<n-1; i++)
        {
            int a,b;cin >> a >> b;
            svi_putevi[i].fi = a;
            svi_putevi[i].sc = b;
            graf[a].pb(b);
            graf[b].pb(a);
        }
        dfs(1,1,0);
        fillUp();
        for(int i=0; i<m; i++)
        {
            int x;cin >> x;
            vector<pii> v(x);
            for(int j=0; j<x; j++)
            {
                cin >> v[j].sc;
                v[j].fi = tin[v[j].sc];
            }
            sort(all(v));
            reverse(all(v));
            //for(auto x: v)cout << x.sc << " "; cout << endl;
            int cale = lca(v[0].sc, v[1].sc);
            cnt[v[0].sc] ++;
            cnt[v[1].sc] ++;
            cnt[cale] -=2;
            for(int j=2; j<x; j++)
            {
                cnt[cale]++;
                cnt[v[j].sc]++;
                cale = lca(cale, v[j].sc);
                cnt[cale]-=2;
            }
        }
        dfs2(1,1);
        int rez = 0;
        for(int i=1; i<=n; i++)if(cnt[i]>=k)rez++;
        cout << rez << endl;
        for(int i=0; i<n-1; i++)
        {
            int a = svi_putevi[i].fi;
            int b = svi_putevi[i].sc;
            if(dist[a] > dist[b])swap(a,b);
            if(cnt[b] >= k)cout << i + 1 << " ";
        }

    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...