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;
}