크리스마스 트리 (JUNGOL 6131)

https://jungol.co.kr/problem/6131

---

아이디어

만약 트리가 고정되어있다고 생각해봅시다. 그리고 루트노드는 리프노드가 아니라고 해봅시다. 일단 리프노드가 홀수개이면 절대 불가능합니다. 만약 짝수개라면 각각의 간선마다 몇번 지나는지 셀 수 있습니다. 그 간선이 node-par[node]를 잇는다면, node를 루트로 하는 서브트리에서 리프노드의 개수를 cnt[node]라 할때, cnt[node]가 홀수라면 그 간선은 한번, 짝수라면 두번 지나게 됩니다. 즉, 루트가 아닌 모든 노드에 대해서 cnt[node]가 홀수면 1, 짝수면 2를 전체 값에 더해주면 됩니다.

 

그러면 이를 어떻게 빠르게 갱신할 수 있을까요? ETT와 HLD와 느리게 갱신되는 세그먼트 트리를 이용해주면 됩니다. 어떤 점에 대해서 그 노드에 리프노드가 하나 붙는다면, 그 노드와 조상들에 대해서 cnt값에 1씩 더해주면 됩니다. 이는 O(log^2 N)에 처리할 수 있습니다. 그리고 마지막에는 전체 cnt에서 홀수의 개수를 세어주면 됩니다. 

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

vector <ll> Graph[101010];
ll Sz[101010]={0},top[101010]={0},par[101010]={0},In[101010]={0},cnt=0;

void DFS1(ll node)
{
    Sz[node]=1;
    ll N=Graph[node].size();

    vector <ll> temp;

    for (ll i=0;i<N;i++)
    {
        if (Sz[Graph[node][i]]) continue;
        temp.push_back(Graph[node][i]);
        DFS1(Graph[node][i]);
        par[Graph[node][i]]=node;
        Sz[node]+=Sz[Graph[node][i]];
    }

    Graph[node]=temp; //이제 Graph에는 부모노드가 없음
    N=Graph[node].size();
    for (ll i=0;i<N;i++)
    {
        if (Sz[Graph[node][i]]*2>=Sz[node])
            swap(Graph[node][0],Graph[node][i]);
    }
}
void DFS2(ll node)
{
    In[node]=++cnt;
    
    ll N=Graph[node].size();
    for (ll i=0;i<N;i++)
    {
        if (i==0) top[Graph[node][i]]=top[node];
        else top[Graph[node][i]]=Graph[node][i];
        DFS2(Graph[node][i]);
    }
}

ll tree[404040]={0},lazy[404040]={0}; // tree[i]: i를 루트로 하는 서브트리에서 리프노드가 홀수개이면 1, 아니면 0
void pp(ll s,ll e,ll node)
{
    if (lazy[node]%2==0)
    {
        lazy[node]=0;
        return;
    }
    lazy[node]=1;
    tree[node]=(e-s+1)-tree[node];
    if (s!=e)
    {
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
}
void change(ll s,ll e,ll node,ll l,ll r)
{
    pp(s,e,node);
    if (e<l || r<s) return;
    if (l<=s && e<=r)
    {
        lazy[node]=1;
        pp(s,e,node);
        return;
    }
    ll mid=(s+e)/2;
    change(s,mid,node*2,l,r);
    change(mid+1,e,node*2+1,l,r);
    tree[node]=tree[node*2]+tree[node*2+1];
}
ll Get(ll s,ll e,ll node,ll idx)
{
    pp(s,e,node);
    if (idx<s || e<idx) return 0;
    if (s==e) return tree[node];
    ll mid=(s+e)/2;
    return Get(s,mid,node*2,idx)+Get(mid+1,e,node*2+1,idx);
}

ll N;
void updateNode(ll node)
{
    while (node!=0)
    {
        change(1,N,1,In[top[node]],In[node]);
        node=par[top[node]];
    }
}

bool ck[101010]={0};
ll arr[101010]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll Q,i,a,b;

    cin>>N>>Q;
    for (i=0;i<N-1;i++)
    {
        cin>>a>>b;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    ll root;
    for (i=1;i<=N;i++)
    {
        if (Graph[i].size()!=1)
            root=i;
    }

    DFS1(root);
    top[root]=root;
    DFS2(root);

    for (i=1;i<=N;i++)
    {
        if (Graph[i].size()==0) //리프노드이면
            updateNode(i);
    }

    for (i=0;i<Q;i++)
    {
        ll M;
        cin>>M;

        for (ll j=0;j<M;j++)
        {
            cin>>arr[j];

            if (Graph[arr[j]].size()!=0) //리프노드가 아니면
                updateNode(arr[j]);
            else if (ck[arr[j]]) //리프노드인데 방문했다면
                updateNode(arr[j]);
            else //리프노드인데 방문하지 않았다면
                ck[arr[j]]=true;
        }

        if (Get(1,N,1,1)%2==1) //리프노드가 홀수개라면
            cout<<"-1\n";
        else
        {
            ll temp=tree[1];
            cout<<(temp+M)+2*(N-temp-1)<<"\n";
        }

        for (ll j=0;j<M;j++)
        {
            updateNode(arr[j]);
            if (ck[arr[j]])
                updateNode(arr[j]),ck[arr[j]]=false;
        }
    }
}