fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3.  
  4. #define __Shibae__      signed main()
  5. #define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define fiopen(Path)    freopen(Path".INP", "r", stdin); freopen(Path".OUT", "w", stdout);
  7. #define fipen(Path)     freopen(Path".INP", "r", stdin);
  8. #define sz(s)           (int)s.size()
  9. #define all(x)          x.begin(), x.end()
  10. #define getBit(x, k)    (((x) >> (k)) & 1)
  11. #define ll              long long
  12. #define ii              pair<int, int>
  13. #define fi              first
  14. #define se              second
  15. #define FOR(i, a, b)    for(int i = a, _b = b; i <= _b; i++)
  16. #define FOD(i, a, b)    for(int i = a, _b = b; i >= _b; i--)
  17. #define REP(i, n)       for(int i = 0; i < (n); i++)
  18. #define pb              push_back
  19. #define fau(x, a)       for(auto &x : a)
  20.  
  21. using namespace std;
  22.  
  23. const int MAX = 100005;
  24. const int lg = 18;
  25.  
  26. int n, m;
  27. ll k;
  28.  
  29. vector<ii> g[MAX];
  30.  
  31. int par[MAX][lg];
  32. int h[MAX];
  33. int tin[MAX];
  34. int timer;
  35.  
  36. ll f[MAX];
  37. int idx[MAX];
  38.  
  39. void input()
  40. {
  41.     cin >> n >> m >> k;
  42.  
  43.     FOR(i, 1, n - 1)
  44.     {
  45.         int u, v;
  46.         cin >> u >> v;
  47.         g[u].pb({v, i});
  48.         g[v].pb({u, i});
  49.     }
  50. }
  51.  
  52. void dfs(int u, int pre, int id)
  53. {
  54.     tin[u] = ++timer;
  55.     par[u][0] = pre;
  56.     idx[u] = id;
  57.  
  58.     FOR(i, 1, lg - 1)
  59.         par[u][i] = par[par[u][i - 1]][i - 1];
  60.  
  61.     for (auto [v, eid] : g[u])
  62.     {
  63.         if (v == pre) continue;
  64.         h[v] = h[u] + 1;
  65.         dfs(v, u, eid);
  66.     }
  67. }
  68.  
  69. int lca(int u, int v)
  70. {
  71.     if (h[u] < h[v]) swap(u, v);
  72.  
  73.     int d = h[u] - h[v];
  74.  
  75.     REP(i, lg)
  76.         if (getBit(d, i))
  77.             u = par[u][i];
  78.  
  79.     if (u == v) return u;
  80.  
  81.     FOD(i, lg - 1, 0)
  82.     {
  83.         if (par[u][i] != par[v][i])
  84.         {
  85.             u = par[u][i];
  86.             v = par[v][i];
  87.         }
  88.     }
  89.  
  90.     return par[u][0];
  91. }
  92.  
  93. bool cmp(int u, int v)
  94. {
  95.     return tin[u] < tin[v];
  96. }
  97.  
  98. void calc(int u, int pre)
  99. {
  100.     for (auto [v, id] : g[u])
  101.     {
  102.         if (v == pre) continue;
  103.         calc(v, u);
  104.         f[u] += f[v];
  105.     }
  106. }
  107.  
  108. void solve()
  109. {
  110.     dfs(1, 1, 0);
  111.  
  112.     FOR(i, 1, m)
  113.     {
  114.         int x;
  115.         cin >> x;
  116.  
  117.         vector<int> vertex(x);
  118.  
  119.         REP(j, x)
  120.             cin >> vertex[j];
  121.  
  122.         if (x <= 1) continue;
  123.  
  124.         sort(all(vertex), cmp);
  125.         vertex.erase(unique(all(vertex)), vertex.end());
  126.  
  127.         x = sz(vertex);
  128.  
  129.         if (x <= 1) continue;
  130.  
  131.         REP(j, x)
  132.         {
  133.             int u = vertex[j];
  134.             int v = vertex[(j + 1) % x];
  135.             int p = lca(u, v);
  136.  
  137.             f[u]++;
  138.             f[v]++;
  139.             f[p] -= 2;
  140.         }
  141.     }
  142.  
  143.     calc(1, 1);
  144.  
  145.     vector<int> res;
  146.  
  147.     FOR(i, 2, n)
  148.     {
  149.         if (f[i] / 2 >= k)
  150.             res.pb(idx[i]);
  151.     }
  152.  
  153.     sort(all(res));
  154.  
  155.     cout << sz(res) << "\n";
  156.     fau(x, res)
  157.         cout << x << " ";
  158. }
  159.  
  160. __Shibae__
  161. {
  162.     IOS
  163.     fiopen("SUADUONG");
  164.  
  165.     input();
  166.     solve();
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0.01s 6408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qaTvta
language:
C++ (gcc 8.3)
created:
23 hours 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!