Submission #1288929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288929		loom	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1096 ms	327680 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int N = 1e5+1;
vector<int> g[N], gvt[N];
int dp[N], odd[N], eve[N], dep[N], up[N][18], tin[N], sz[N];
int ans, fans, cnt;

void dfs(int v, int p){
   tin[v] = cnt++;
   if(g[v].size() == 1) dp[v] = 1;

   for(int ch : g[v]){
      if(ch == p) continue;

      dep[ch] = dep[v] + 1;
      up[ch][0] = v;

      dfs(ch, v);
      dp[v] += dp[ch];

      if(dp[ch] % 2 == 0) ans++;
   }
}

void dfs2(int v, int p){
   odd[v] = odd[p];
   eve[v] = eve[p];

   (dp[v] % 2 ? odd[v] : eve[v])++;

   for(int ch : g[v]){
      if(ch != p) dfs2(ch, v);
   }
}

void dfs3(int v){
   for(int ch : gvt[v]){
      dfs3(ch);
      sz[v] += sz[ch];

      if(sz[ch] % 2) fans += odd[ch] - odd[v] - (eve[ch] - eve[v]);
   }
}

int lca(int x, int y){
   if(dep[x] > dep[y]) swap(x, y);

   int k = dep[y] - dep[x];
   for(int i = 0; i < 18; i++) if(k & 1<<i) y = up[y][i];

   if(x == y) return x;

   for(int i = 17; i >= 0; i--){
      if(up[x][i] == up[y][i]) continue;

      x = up[x][i];
      y = up[y][i];
   }

   return up[x][0];
}

bool cmp(int x, int y){
   return tin[x] < tin[y];
}

void solve(){
   int n, q;
   cin>>n>>q;

   for(int i = 1; i < n; i++){
      int x, y;
      cin>>x>>y;
      g[x].push_back(y);
      g[y].push_back(x);
   }

   int r, tot = 0;
   for(int i = 1; i <= n; i++){
      if(g[i].size() > 1) r = i;
      else tot++;
   }
   r = 2;

   up[r][0] = r;
   dfs(r, 0);
   dfs2(r, 0);

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

   while(q--){
      int m;
      cin>>m;

      vector<int> v(m);
      for(int &x : v) cin>>x;

      auto l = v;

      sort(v.begin(), v.end(), cmp);

      for(int i = 1; i < m; i++){
         v.push_back(lca(v[i-1], v[i]));
      }

      sort(v.begin(), v.end(), cmp);
      v.erase(unique(v.begin(), v.end()), v.end());

      for(int x : v){
         sz[x] = (g[x].size() == 1 ? -1 : 0);
         gvt[x].clear();
      }

      for(int x : l) sz[x]++;

      for(int i = 1; i < m; i++){
         gvt[lca(v[i-1], v[i])].push_back(v[i]);
      }

      fans = ans + n + m - 1;
      r = v[0];

      dfs3(r);
      cout<<((tot + sz[r]) % 2 == 0 ? fans : -1)<<nl;
   }
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30