讲解 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)\)。

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

完整代码：

<code>#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;

}