fork download
copy 
  1. /*
  2. Lord Jesus, grant me clarity and patience to write clean code.
  3. Buddha, help my mind be calm and mindful so I see the errors before they happen.
  4. Allah, guide my hands on the straight path of logic, free from bugs and confusion.
  5. May every compile be smooth, and every run be successful.
  6. Amen. So be it. Ameen.
  7. */
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. typedef long long ll;
  11. typedef pair<ll,ll> pll;
  12. typedef pair<ll,pll> lll;
  13. typedef array<ll,3> arr3;
  14. typedef pair<ll,arr3> pq3;
  15. #define fi first
  16. #define se second
  17.  
  18. const ll maxN = 1e5 + 5, maxM = 5e4 + 5, maxLog = 20;
  19.  
  20. ll n, h [maxN], st [maxN], en [maxN], pr [maxN] [maxLog], cnt, t, f [maxN], m, k, f2 [maxN];
  21. vector <ll> adj [maxN], ver;
  22. stack <ll> sta;
  23. vector <pll> edge;
  24.  
  25. void dfs (ll x, ll par) {
  26.     h [x] = h [par] + 1;
  27.     pr [x] [0] = par;
  28.     for (int i = 1; i < maxLog; i ++) pr [x] [i] = pr [pr [x] [i - 1]] [i - 1];
  29.     st [x] = ++ cnt;
  30.     for (ll i : adj [x]) if (i != par) dfs (i, x);
  31.     en [x] =    cnt;
  32. }
  33.  
  34. ll lca (ll x, ll y) {
  35.     if (h [x] < h [y]) swap (x, y);
  36.     if (h [x] > h [y]) {
  37.         ll dis = h [x] - h [y];
  38.         for (int i = 0; i < maxLog; i ++) if ((dis >> i) & 1) x = pr [x] [i];
  39.     }
  40.     if (x == y) return x;
  41.     for (int i = maxLog - 1; ~i; i --) {
  42.         if (pr [x] [i] != pr [y] [i]) {
  43.             x = pr [x] [i];
  44.             y = pr [y] [i];
  45.         }
  46.     }
  47.     return pr [x] [0];
  48. }
  49.  
  50. bool cmp (ll x, ll y) {return st [x] < st [y];}
  51.  
  52. void build () {
  53.     t = ver. size ();
  54.     if (t < 2) {
  55.         ver. clear ();
  56.         return;
  57.     }
  58.     sort (ver. begin (), ver. end (), cmp);
  59.     for (int i = 1; i < t; i ++) ver. push_back (lca (ver [i], ver [i - 1]));
  60.     sort (ver. begin (), ver. end (), cmp);
  61.     ver. erase (unique (ver. begin (), ver. end ()), ver. end ());
  62.     sta. push (ver [0]);
  63.     for (int i = 1; i < ver. size (); i ++) {
  64.         f [ver [i]] ++;
  65.         //cerr << ver [i] << '+' << '\n';
  66.         while (en [sta. top ()] < st [ver [i]]) sta. pop ();
  67.         f [sta. top ()] --;
  68.         //cerr << sta. top ()<< '-' << '\n';
  69.         sta. push (ver [i]);
  70.     }
  71.     while (!sta. empty ()) sta. pop ();
  72.     ver. clear ();
  73. }
  74.  
  75. void dfs2 (ll x, ll par) {
  76.     for (ll i : adj [x]) if (i != par) {
  77.         dfs2 (i, x);
  78.         f2 [x] += f [i];
  79.     }
  80.     f [x] += f2 [x];
  81. }
  82.  
  83. signed main () {
  84.     ios::sync_with_stdio (0);
  85.     cin. tie (0);
  86.     cout. tie (0);
  87.     #define task "untitled1"
  88.     if (fopen (task".inp", "r")) {
  89.         freopen (task".inp", "r", stdin );
  90.         freopen (task".out", "w", stdout);
  91.     }
  92.     cin >> n >> m >> k;
  93.     for (int i = 1, u, v; i < n; i ++) {
  94.         cin >> u >> v;
  95.         adj [u]. push_back (v);
  96.         adj [v]. push_back (u);
  97.         edge. push_back ({u, v});
  98.     }
  99.     dfs (1, 0);
  100.     for (int c, x; m; m --) {
  101.         cin >> c;
  102.         for (;c;c --) {
  103.             cin >> x;
  104.             ver. push_back (x);
  105.         }
  106.         //for (ll i : ver) cerr << i << ' '; cerr << '\n';
  107.         build ();
  108.         //for (int i = 1; i <= n; i ++) cerr << f [i] << ' '; cerr << '\n';
  109.     }
  110.     dfs2 (1, 0);
  111.     //for (int i = 1; i <= n; i ++) cerr << f [i] << ' '; cerr << '\n';
  112.     vector <ll> ans;
  113.     cnt = 0;
  114.     for (pll i : edge) {
  115.         cnt ++;
  116.         if (i. fi == pr [i. se] [0] && f2 [i. fi] >= k && f [i. se] >= k) ans. push_back (cnt);
  117.         else if (f2 [i. se] >= k && f [i. fi] >= k) ans. push_back (cnt);
  118.     }
  119.     cout << ans. size () << '\n';
  120.     for (ll i : ans) cout << i << ' ';
  121. }
  122.  
Success #stdin #stdout 0.01s 8652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/d0FH4n
language:
C++14 (gcc 8.3)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!