This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN=1e5+5;
const int MAXLOG=21;
int n,q;
vector<int> adj[MAXN];
bool leaf[MAXN];
int root=1;
int subLf[MAXN];
int depth[MAXN];
int cnt1[MAXN], cnt2[MAXN];
int ansOrg=0;
int tin[MAXN];
int order[2*MAXN];
int timer=0;
int lg2[2*MAXN];
int spT[2*MAXN][MAXLOG];
unordered_set<int> s;
int newCnt[MAXN];
vector<int> virtNodes;
vector<int> vAdj[MAXN];
int used[MAXN];
void dfs(int v,int par)
{
subLf[v]=0;
if(leaf[v]) subLf[v]=1;
for(auto u: adj[v])
{
if(u==par) continue;
depth[u]=depth[v]+1;
dfs(u,v);
subLf[v]+=subLf[u];
}
}
void dfs2(int v,int par)
{
if(subLf[v]&1==1) cnt1[v]++;
else cnt2[v]++;
for(auto u: adj[v])
{
if(u==par) continue;
cnt1[u]=cnt1[v];
cnt2[u]=cnt2[v];
dfs2(u,v);
}
}
void dfs3(int v,int par)
{
order[++timer]=v;
tin[v]=timer;
for(auto u: adj[v])
{
if(u==par) continue;
dfs3(u,v);
order[++timer]=v;
}
}
void sparseTable()
{
lg2[0]=-1;
for(int i=1;i<=timer;i++)
{
lg2[i]=lg2[i>>1]+1;
spT[i][0]=order[i];
}
for(int j=1;(1<<j)<=timer;j++)
{
for(int i=1;i<=timer;i++)
{
if(i+(1<<(j-1))>timer) break;
spT[i][j]=spT[i][j-1];
if(depth[spT[i+(1<<(j-1))][j-1]]<depth[spT[i][j-1]]) spT[i][j]=spT[i+(1<<(j-1))][j-1];
}
}
}
int lca(int u,int v)
{
if(tin[u]>tin[v]) swap(u,v);
int d=tin[v]-tin[u]+1;
int c1=spT[tin[u]][lg2[d]];
int c2=spT[tin[v]-(1<<lg2[d])+1][lg2[d]];
if(depth[c1]<=depth[c2]) return c1;
return c2;
}
bool cmp(int u,int v)
{
return tin[u]<tin[v];
}
int buildVirtTree()
{
for(auto v: virtNodes) used[v]=1;
sort(virtNodes.begin(), virtNodes.end(), cmp);
int sz=virtNodes.size();
for(int i=1;i<sz;i++)
{
virtNodes.push_back(lca(virtNodes[i-1], virtNodes[i]));
}
sort(virtNodes.begin(), virtNodes.end(), cmp);
vector<int> nodes;
for(auto v: virtNodes)
{
if(!nodes.empty() && nodes.back()!=v) nodes.push_back(v);
if(nodes.empty()) nodes.push_back(v);
}
for(auto v: nodes) vAdj[v].clear();
vector<int> st;
for(auto v: nodes)
{
while(!st.empty() && lca(st.back(), v)!=st.back()) st.pop_back();
if(!st.empty())
{
vAdj[st.back()].push_back(v);
}
st.push_back(v);
}
return st[0];
}
pair<int,int> dfs_virt(int v,int par)
{
int ret=0;
int cntUsed=used[v];
for(auto u: vAdj[v])
{
auto cur=dfs_virt(u,v);
ret+=cur.first;
cntUsed+=cur.second;
}
if(cntUsed&1==1)
{
int cntOdd=cnt1[v]-cnt1[par];
int cntEv=cnt2[v]-cnt2[par];
ret+=cntOdd-cntEv;
}
return {ret, cntUsed};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>q;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(adj[i].size()==1) leaf[i]=1;
else root=i;
}
depth[root]=1;
dfs(root,-1);
dfs2(root,-1);
dfs3(root,-1);
sparseTable();
for(int i=1;i<=n;i++)
{
if(i==root) continue;
if(subLf[i]&1==1) ansOrg+=1;
else ansOrg+=2;
}
for(int tt=0;tt<q;tt++)
{
int d;
cin>>d;
for(int i=0;i<d;i++)
{
int v;
cin>>v;
newCnt[v]++;
s.insert(v);
}
int ans=ansOrg+d;
for(auto v: s)
{
if(leaf[v]) newCnt[v]--;
if(newCnt[v]&1==1) virtNodes.push_back(v);
}
if((subLf[root]+virtNodes.size())&1==1) cout<<-1<<endl;
else
{
if(virtNodes.size()>0)
{
int virtRoot=buildVirtTree();
ans+=dfs_virt(virtRoot,root).first;
for(auto v: virtNodes) used[v]=0;
}
cout<<ans<<endl;
}
for(auto v: s) newCnt[v]=0;
s.clear();
virtNodes.clear();
}
return 0;
}
Compilation message (stderr)
cleaning.cpp: In function 'void dfs2(int, int)':
cleaning.cpp:48:18: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
48 | if(subLf[v]&1==1) cnt1[v]++;
| ~^~~
cleaning.cpp: In function 'std::pair<int, int> dfs_virt(int, int)':
cleaning.cpp:154:17: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
154 | if(cntUsed&1==1)
| ~^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:196:18: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
196 | if(subLf[i]&1==1) ansOrg+=1;
| ~^~~
cleaning.cpp:217:23: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
217 | if(newCnt[v]&1==1) virtNodes.push_back(v);
| ~^~~
cleaning.cpp:220:40: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
220 | if((subLf[root]+virtNodes.size())&1==1) cout<<-1<<endl;
| ~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |