Submission #1293663

#TimeUsernameProblemLanguageResultExecution timeMemory
1293663HoriaHaivasSpring cleaning (CEOI20_cleaning)C++20
34 / 100
1097 ms50020 KiB
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

priority_queue<int> pqmax[200005];
priority_queue<int> pqmin[200005];
vector<int> nodes[200005];
int h[200005];
int u[200005];
int leaves[200005];
int ans;
bool ok;

void dfs(int node, int parent)
{
    leaves[node]=0;
    if (nodes[node].size()==1 && parent!=-1)
    {
        leaves[node]=1;
        pqmax[node].push(h[node]);
        pqmin[node].push(-h[node]);
        return;
    }
    int min1,min2,sum;
    min1=1e9;
    min2=1e9;
    sum=0;
    for (auto x : nodes[node])
    {
        if (x!=parent)
        {
            h[x]=h[node]+1;
            dfs(x,node);
            leaves[node]+=leaves[x];
            while (!pqmax[x].empty())
            {
                sum+=pqmax[x].top();
                pqmax[x].pop();
            }
            if (-pqmin[x].top()<min1)
            {
                min2=min1;
                min1=-pqmin[x].top();
            }
            else if (-pqmin[x].top()<min2)
            {
                min2=-pqmin[x].top();
            }
            while (!pqmin[x].empty())
            {
                pqmin[x].pop();
            }
        }
    }
    if (parent!=-1)
    {
        if (leaves[node]%2==0)
        {
            ans+=(sum-min1-min2)-(h[node]*(leaves[node]-2));
            pqmin[node].push(-min1);
            pqmin[node].push(-min2);
            pqmax[node].push(min1);
            pqmax[node].push(min2);
            leaves[node]=2;
        }
        else
        {
            ans+=(sum-min1)-(h[node]*(leaves[node]-1));
            pqmin[node].push(-min1);
            pqmax[node].push(min1);
            leaves[node]=1;
        }
    }
    else
    {
        if (leaves[node]%2==0)
            ans+=sum-h[node]*leaves[node];
        else
            ok=false;
        leaves[node]=0;
    }
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,uu,v,root,d;
    cin >> n >> q;
    for (i=1; i<=n-1; i++)
    {
        cin >> uu >> v;
        nodes[uu].push_back(v);
        nodes[v].push_back(uu);
    }
    for (i=1; i<=n; i++)
    {
        if (nodes[i].size()!=1)
        {
            root=i;
            break;
        }
    }
    for (i=1;i<=q;i++)
    {
         cin >> d;
         for (j=1;j<=d;j++)
         {
              cin >> u[j];
              nodes[u[j]].push_back(n+j);
              nodes[n+j].push_back(u[j]);
         }
         h[root]=0;
         ok=true;
         ans=0;
         dfs(root,-1);
         if (ok)
         cout << ans << "\n";
         else
         cout << "-1\n";
         for (j=1;j<=d;j++)
         {
              nodes[u[j]].pop_back();
              nodes[n+j].pop_back();
         }
    }
    return 0;
}
#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...