제출 #1290048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290048		loom	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	132 ms	33020 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], tin[N], sz[N], up[N][17];
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){
   for(int ch : g[v]){
      if(ch == p) continue;

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

      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 < 17; i++) if(k & 1<<i) y = up[y][i];

   if(x == y) return x;

   for(int i = 16; 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;
   for(int i = 1; i <= n; i++) if(g[i].size() > 1) r = i;

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

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

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

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

      auto l = v;

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

      for(int i = 1; i < d; 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 < v.size(); i++){
         gvt[lca(v[i-1], v[i])].push_back(v[i]);
      }

      fans = ans + n + d - 1;
      int vr = v[0];

      dfs3(vr);
      if(sz[vr] % 2) fans += odd[vr] - odd[r] - (eve[vr] - eve[r]);

      cout<<((dp[r] + sz[vr]) % 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: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30