P6805 [CEOI2020] 春季大扫除

思路:

首先随意钦定一个不是叶子节点的节点为根节点。

然后考虑对于一个不是根节点的点 \(u\),肯定需要至少一个叶子去与 \(u\) 子树之外的叶子节点配对。

考虑 \(u\)\(fa_u\) 的这条边,首先至少有一个叶子节点穿过,然后设 \(p_u\) 表示 \(u\) 中的叶子节点个数:

  • \(p_u\) 为偶,在一个叶子节点往外传后还剩奇数个,两两配对后还剩一个叶子节点,也需要往外传经过 \(u \to fa_u\) 的这条边。

  • 否则 \(p_u\) 为奇时,在一个叶子节点往外传后还剩偶数个,可以完美两两配对。

那么对于 \(u \to fa_u\) 的这条边,经过这条边的叶子节点个数为 \(1 + [p_u \bmod 2=0]\)

则总答案为:

\[\sum_{u \ne rt} 1 + [p_u \bmod 2 = 0] = (n-1) + \sum_{u \ne rt} [p_u \bmod 2 = 0] \]

考虑将 \(u \ne rt\) 给去掉,可以方便一些计算。

因为若 \(p_{rt}\) 不为偶数,就无法使得所有叶子节点配对,即无解,所以在有解的情况下 \([p_{rt} \bmod 2 = 0] = 1\),则需要将前面 \(-1\)

则原式化为:

\[n -2 + \Big(\sum_u[p_u \bmod 2 = 0]\Big) \]

则每次在 \(u\) 处添加一个叶子节点,就相当于将 \(u\) 到根节点的 \(p_u \bmod 2\) 的值取反。

那么直接树剖维护即可,时间复杂度为 \(O(\Big(\sum D_i\Big) \log^2 n)\)

要注意一下细节:在叶子节点下添加新节点,是没有贡献的(即不需要翻转),于是我们可以动态维护每个点的度数。

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,s,q,x,h,rt;
ll du[N];
bool f[N];
vector<ll> E[N];
stack<ll> T;
void add(ll u,ll v){
    E[u].push_back(v);
    E[v].push_back(u);
    du[u]++,du[v]++;
}
namespace Seg{
    struct Node{
        ll len;
        ll l,r;
        ll data;
        bool tag;
    }X[N<<2];
    void pushup(ll k){
        X[k].data=X[k<<1].data+X[k<<1|1].data;
    }
    void rev(ll k){
        X[k].data=X[k].len-X[k].data;
        X[k].tag^=1ll;
    }
    void push_down(ll k){
        if(X[k].tag){
            rev(k<<1);
            rev(k<<1|1);
            X[k].tag=0;
        }
    }
    void build(ll k,ll l,ll r){
        X[k].len=r-l+1;
        X[k].l=l,X[k].r=r;
        if(l==r)
          return ;
        ll mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    void update(ll k,ll i){
        if(X[k].l==i&&i==X[k].r){
            X[k].data=1;
            return ;
        }
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          update(k<<1,i);
        else
          update(k<<1|1,i);
        pushup(k);
    }
    void rev(ll k,ll l,ll r){
        if(X[k].l==l&&r==X[k].r){
            rev(k);
            return ;
        }
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          rev(k<<1,l,r);
        else if(l>mid)
          rev(k<<1|1,l,r);
        else{
            rev(k<<1,l,mid);
            rev(k<<1|1,mid+1,r);
        }
        pushup(k);
    }
    ll sum(){
        return X[1].data;
    }
};
namespace Tree{
    ll cnt=0;
    ll siz[N],w[N],z[N],fa[N],d[N],t[N],dfn[N];
    void dfs1(ll u,ll f){
        siz[u]=1;
        for(auto v:E[u]){
            if(v==f)
              continue;
            fa[v]=u;
            d[v]=d[u]+1;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[z[u]])
              z[u]=v;
        }
    }
    void dfs2(ll u,ll k){
        t[u]=k;
        dfn[u]=++cnt;
        if(!z[u])
          return ;
        dfs2(z[u],k);
        for(auto v:E[u]){
            if(v==fa[u]||v==z[u])
              continue;
            dfs2(v,v);
        }
    }
    void dfs3(ll u){
        if(du[u]==1){
            s++;
            w[u]=1;
            return ;
        }
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            dfs3(v);
            w[u]+=w[v];
        }
    }
    void init(){
        Seg::build(1,1,n);
        dfs1(rt,rt);
        dfs2(rt,rt);
        dfs3(rt);
        For(i,1,n)
          if((w[i]&1ll)^1ll)
            Seg::update(1,dfn[i]);
    }
    void rev(ll u,ll v){
        while(t[u]!=t[v]){
            if(d[t[u]]<d[t[v]])
              swap(u,v);
            Seg::rev(1,dfn[t[u]],dfn[u]);
            u=fa[t[u]];
        }
        if(d[u]>d[v])
          swap(u,v);
        Seg::rev(1,dfn[u],dfn[v]);
    }
};
bool End;
int main(){
    n=read(),q=read();
    for(int u,v,i=1;i<n;i++){
        u=read(),v=read();
        add(u,v);
    }
    For(i,1,n){
        if(du[i]!=1){
            rt=i;
            break;
        }
    }
    Tree::init();
    while(q--){
        h=0;
        m=read();
        For(i,1,m){
            x=read();
            if(du[x]==1)
              s--;
            else{
                Tree::rev(x,rt);
                f[x]^=1ll;
            }
            s++;
            du[x]++;
            T.push(x);
        }
        if(s&1ll)
          puts("-1");
        else{
            write(h+n+m-2+Seg::sum());
            putchar('\n');
        }
        while(!T.empty()){
            x=T.top();
            s--;
            du[x]--;
            if(du[x]==1)
              s++;
            if(f[x]){
                Tree::rev(rt,x);
                f[x]=0;
            }
            T.pop();
        }
    }
	//cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

热门相关:特工皇后不好惹   辰少的霸道专宠:强婚88次   末日终战   豪门宠婚:权少夫人萌上天   退婚后我嫁给了前任他叔