Submission #1361801

#TimeUsernameProblemLanguageResultExecution timeMemory
1361801m5588ohammedSpring cleaning (CEOI20_cleaning)C++20
0 / 100
89 ms26420 KiB
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mod 1000000007
#define int long long
int n,q;
int arr[100005],depth[100005],t[20][100005],entry[100005],exsi[100005],siz[100005],ent,exs,Oans;
array <int,2> pre[100005];
vector <int> v[100005],vr[100005];
int LCA(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    int k=depth[a]-depth[b];
    for(int bt=19;bt>=0;bt--){
        if(k-(1ll<<bt)>=0){
            k-=(1ll<<bt);
            a=t[bt][a];
        }
    }
    for(int bt=19;bt>=0;bt--){
        if(t[bt][a]!=t[bt][b]){
            a=t[bt][a];
            b=t[bt][b];
        }
    }
    if(a==b) return a;
    return t[0][a];
}
void dfs1(int i,int last){
    if((int)v[i].size()==1) siz[i]=1;
    for(int j:v[i]){
        if(j==last) continue;
        dfs1(j,i);
        siz[i]=(siz[i]+siz[j])%2;
    }
    if(i!=1) Oans+=2-siz[i]%2;
    return;
}
void dfs2(int i,int last){
    t[0][i]=last;
    depth[i]=depth[t[0][i]]+1;
    entry[i]=ent++;
    for(int j:v[i]){
        if(j==last) continue;
        dfs2(j,i);
    }
    pre[0][i]=pre[0][last]+(1-siz[i]%2);
    pre[1][i]=pre[1][last]+siz[i]%2;
    exsi[i]=exs++;
    return;
}
array <int,2> calc(int i,int last){
    array <int,2> ans={0,0};
    if(vr[i].size()==0) ans[1]=1;
    for(int j:vr[i]){
        array <int,2> a=calc(j,i);
        ans[0]+=a[0];ans[1]=(ans[1]+a[1])%2;
    }    
    if(i!=1){
        if(ans[1]==1) ans[0]+=(pre[1][i]-pre[1][last])-(pre[0][i]-pre[0][last]);
    }
    return ans;
}
int answer_virtual(vector <int> leafs){
    set <array<int,2>> ord;
    for(int i=0;i<leafs.size();i++){
        ord.insert({entry[leafs[i]],leafs[i]});
        if(i!=0){
            int C=LCA(leafs[i],leafs[i-1]);
            ord.insert({entry[C],C});
        }
    }
    ord.insert({entry[1],1});
    vector <int> stack;
    int rt;
    for(auto [idx,i]:ord){
        if(stack.size()==0){
            rt=i;
            stack.push_back(i);
        }
        else{
            while(exsi[i]>exsi[stack.back()]||entry[i]<entry[stack.back()]){
                stack.pop_back();
            }
            vr[stack.back()].push_back(i);
            stack.push_back(i);
        }
    }
    array <int,2> u=calc(rt,0);
    int ans=Oans+u[0];

    for(auto [idx,i]:ord){
        vr[i].clear();
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int bt=1;bt<=19;bt++){
        for(int i=1;i<=n;i++){
            t[bt][i]=t[bt-1][t[bt-1][i]];
        }
    }
    while(q--){
        int k;
        cin>>k;
        vector <int> leafs,vc;
        for(int i=0;i<k;i++){
            int a;cin>>a;
            vc.push_back(a);
        }
        sort(vc.begin(),vc.end());
        int fre=0,cnt=0;
        for(int i=0;i<k;i++){
            if(i!=0&&vc[i]!=vc[i-1]){
                if(v[vc[i-1]].size()==1){
                    cnt++;
                }
                if(v[vc[i-1]].size()==1&&fre%2==0){
                    leafs.push_back(vc[i-1]);
                }
                if(v[vc[i-1]].size()>0&&fre%2==1){
                    leafs.push_back(vc[i-1]);
                }
                fre=0;
            }
            fre++;
        }
        if(v[vc.back()].size()==1) cnt++;
        if(v[vc.back()].size()==1&&fre%2==0){
            leafs.push_back(vc.back());
        }
        if(v[vc.back()].size()>0&&fre%2==1){
            leafs.push_back(vc.back());
        }
        if((siz[1]+k-cnt)%2==1) cout<<-1<<endl;
        else cout<<answer_virtual(leafs)+k<<endl;;
        leafs.clear();
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...