Submission #1259923

#TimeUsernameProblemLanguageResultExecution timeMemory
1259923abdelhakimSpring cleaning (CEOI20_cleaning)C++20
0 / 100
1097 ms17496 KiB
// #include <bits/stdc++.h>
// #define ll long long
// #define dbg(x) cerr << #x << ' ' <<  x << endl; 
// #define inf 1e18
// using namespace std;

// void printvec(vector<ll>& vec)
// {
//   for (auto &&e : vec)
//   {
//     cout << e << ' ';
//   }
//   cout << endl;
// }
// vector<pair<ll,ll>> parr;
// ll root=0;
// ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans)
// {
//   if(node!=par && adj[node].size()==1)
//   {
//     parr[node]={par,1};
//     return 1;
//   }
//   ll sm=0;
//   vector<ll> l3ibat;
//   for (auto &&e : adj[node])
//   {
//     if(e==par)continue;
//     ll val=solve(adj,e,node,ans);
//     l3ibat.push_back(val);
//     sm+=val;
//     if(val%2)ans++;
//     else ans+=2;
//   }
//   bool equal=true;
//   for (int i=1;i<l3ibat.size();i++)
//   {

//   }
//   if(adj[node].size()==1 && node==0) sm++;
//   parr[node]={par,sm%2};
//   return sm;
// }
// void climb(ll node, ll& ans)
// {
//   while(node!=0)
//   {
//     if(parr[node].second==0)
//     {
//       ans--;
//     }
//     else ans++;
//     parr[node].second^=1;
//     node=parr[node].first;
//   }
// }
// int main()
// {
//   ll n, q;
//   cin>>n>>q;
//   parr.resize(n);
//   vector<vector<ll>> adj(n);
//   for (int i=0;i<n-1;i++)
//   {
//     ll u, v;
//     cin>>u>>v;
//     u--;v--;
//     adj[u].push_back(v);
//     adj[v].push_back(u);
//   }
//   ll old=0;
//   solve(adj,0,0,old);
//   while(q--)
//   {
//     ll d;
//     cin>>d;
//     vector<ll> v;
//     vector<ll> v2(n);
//     ll ans=old;
//     for (int i=0;i<d;i++)
//     {
//       ll nd;
//       cin>>nd;
//       nd--;
//       v.push_back(nd);
//       v2[nd]++;
//       climb(nd,ans);
//     }
//     ll val=0;
//     for (int i=0;i<n;i++)
//     {
//       if(adj[i].size()==1)val+=max(1LL,v2[i]);
//       else val+=v2[i];
//     }
//     if(val%2) cout << -1 << endl;
//     else cout << ans+d << endl;
//     for (auto &&nd : v)
//     {
//       climb(nd,ans);
//     }
//   }
// }

#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr << #x << ' ' <<  x << endl; 
#define inf 1e18
using namespace std;

void printvec(vector<ll>& vec)
{
  for (auto &&e : vec)
  {
    cout << e << ' ';
  }
  cout << endl;
}
vector<pair<ll,ll>> parr;
ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans)
{
  if(node!=par && adj[node].size()==1)
  {
    parr[node]={par,1};
    return 1;
  }
  ll sm=0;
  for (auto &&e : adj[node])
  {
    if(e==par)continue;
    ll val=solve(adj,e,node,ans);
    sm+=val;
    if(val%2)ans++;
    else ans+=2;
  }
  if(adj[node].size()==1 && node==0) sm++;
  parr[node]={par,sm%2};
  return sm;
}
void climb(ll node, ll& ans)
{
  while(node!=0)
  {
    if(parr[node].second==0)
    {
      ans--;
    }
    else ans++;
    parr[node].second^=1;
    node=parr[node].first;
  }
}
int main()
{
  ll n, q;
  cin>>n>>q;
  parr.resize(n);
  vector<vector<ll>> adj(n);
  for (int i=0;i<n-1;i++)
  {
    ll u, v;
    cin>>u>>v;
    u--;v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  ll old=0;
  solve(adj,0,0,old);
  while(q--)
  {
    ll d;
    cin>>d;
    vector<ll> v;
    vector<ll> v2(n);
    ll ans=old;
    for (int i=0;i<d;i++)
    {
      ll nd;
      cin>>nd;
      nd--;
      v.push_back(nd);
      v2[nd]++;
      climb(nd,ans);
    }
    ll val=0;
    for (int i=0;i<n;i++)
    {
      if(adj[i].size()==1)val+=max(1LL,v2[i]);
      else val+=v2[i];
    }
    if(val%2) cout << -1 << endl;
    else cout << ans+d << endl;
    for (auto &&nd : v)
    {
      climb(nd,ans);
    }
  }
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...