fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vll;
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12.  
  13. const int MAXN = 1e5 + 1;
  14. const int N = 1024 * 128;
  15.  
  16. vi graf[N];
  17. int tree[2 * N], lazy[2 * N], ile[MAXN], podd[MAXN], skok[MAXN], pre[MAXN], par[MAXN], odz[MAXN];
  18. int timer = 1, korzen;
  19.  
  20. void dfs(int v, int ojc){
  21.     podd[v] = 1;
  22.     if(graf[v].size() == 1) ile[v]++;
  23.     for(int u : graf[v]){
  24.         if(u == ojc) continue;
  25.         par[u] = v;
  26.         dfs(u, v);
  27.         ile[v] += ile[u];
  28.         podd[v] += podd[u];
  29.     }
  30. }
  31.  
  32. void decompose(int v, int ojc, int pocz){
  33.     odz[timer] = v;
  34.     pre[v] = timer++;
  35.     skok[v] = pocz;
  36.     int mx = 0, ciezki = 0;
  37.     for(int u : graf[v]){
  38.         if(u == ojc) continue;
  39.         if(mx < podd[u]){
  40.             mx = podd[u]; ciezki = u;
  41.         }
  42.     }
  43.  
  44.     if(ciezki) decompose(ciezki, v, pocz);
  45.     for(int u : graf[v]){
  46.         if(u == ojc || u == ciezki) continue;
  47.         decompose(u, v, u);
  48.     }
  49. }
  50.  
  51. void push(int v, int l, int r){
  52.     if(lazy[v]){
  53.         int mid = (l + r) / 2;
  54.         int dl1 = mid - l + 1, dl2 = r - mid;
  55.         tree[2 * v] = dl1 - tree[2 * v];
  56.         tree[2 * v + 1] = dl2 - tree[2 * v + 1];
  57.         lazy[2 * v] ^= 1; lazy[2 * v + 1] ^= 1;
  58.         lazy[v] = 0;
  59.     }
  60. }
  61.  
  62. void zmien(int v, int l, int r, int ql, int qr){
  63.     if(l > qr || r < ql || r < l) return;
  64.     if(ql <= l && r <= qr){
  65.         int dl = r - l + 1;
  66.         tree[v] = dl - tree[v];
  67.         lazy[v] ^= 1;
  68.         return;
  69.     }
  70.  
  71.     push(v, l, r);
  72.  
  73.     int mid = (l + r) / 2;
  74.     zmien(2 * v, l, mid, ql, qr); zmien(2 * v + 1, mid + 1, r, ql, qr);
  75.  
  76.     tree[v] = tree[2 * v] + tree[2 * v + 1];
  77. }
  78.  
  79.  
  80. void upd(int v){
  81.     while(skok[v] != korzen){
  82.         zmien(1, 1, N, pre[skok[v]], pre[v]);
  83.         v = par[skok[v]];
  84.     }
  85.     if(v != korzen){
  86.         zmien(1, 1, N, 2, pre[v]);
  87.     }
  88. }
  89.  
  90. void solve(){
  91.     int d; cin >> d;
  92.     vi t(d);
  93.     for(int i = 0; i < d; i++) cin >> t[i];
  94.     sort(t.begin(), t.end());
  95.     int utrac = 0;
  96.     vi g;
  97.  
  98.     for(int i = 0; i < d; ){
  99.         int j = i;
  100.         while(j < d && t[j] == t[i]) j++;
  101.         int v = t[i];
  102.         int cnt = j - i;
  103.  
  104.         if(graf[v].size() == 1){
  105.             utrac++;
  106.             if(!(cnt & 1)) g.pb(v);
  107.         }else{
  108.             if(cnt & 1) g.pb(v);
  109.         }
  110.         i = j;
  111.     }
  112.  
  113.     if((d + ile[korzen] - utrac) & 1){ cout << "-1\n"; return; }
  114.  
  115.     for(int u : g) upd(u);
  116.     cout << 2 * podd[korzen] - tree[1] + d - 2 << "\n";
  117.     for(int u : g) upd(u);
  118. }
  119.  
  120. void build(int v, int l, int r){
  121.     if(l == r){
  122.         if(l == 1 && l > podd[korzen]) return;
  123.         tree[v] = ile[odz[l]] & 1;
  124.         return;
  125.     }
  126.     int mid = (l + r) / 2;
  127.     build(2 * v, l, mid); build(2 * v + 1, mid + 1, r);
  128.  
  129.     tree[v] = tree[2 * v] + tree[2 * v + 1];
  130. }
  131.  
  132. int main(){
  133.     ios_base::sync_with_stdio(0);
  134.     cin.tie(0);
  135.  
  136.     int n, q;
  137.     cin >> n >> q;
  138.  
  139.     for(int i = 1; i < n; i++){
  140.         int a, b; cin >> a >> b;
  141.         graf[a].pb(b); graf[b].pb(a);
  142.     }
  143.  
  144.     for(int i = 1; i <= n; i++){
  145.         if(graf[i].size() > 1){
  146.             korzen = i; break;
  147.         }
  148.     }
  149.  
  150.     dfs(korzen, 0);
  151.     decompose(korzen, 0, korzen);
  152.     build(1, 1, N);
  153.  
  154.     while(q--) solve();
  155.  
  156.  
  157.  
  158.  
  159.  
  160.     return 0;
  161. }
  162.  
  163.  
Success #stdin #stdout 0.01s 10680KB
comments (?)
stdin
copy 
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
stdout
copy 
-1
8
6
https://ideone.com/WpBrgY
language:
C++ (gcc 8.3)
created:
1 day 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!