P6805 （树上最小路径覆盖思想）

难度3

比较有意思的一道题。首先看到题目是求树上最小路径覆盖，自然想到由叶子入手去分析，所以当子树内有偶数个叶子节点时，那么就有两个叶子向上匹配，否则只有一个叶子向上匹配。这个东西可以用树剖维护，线段树维护的是子树内有多少个偶的，相当于一个区间反转一类的东西。

细节不算多，但也坑了我0.5h，以后在检查时要想好这句话在什么情况下运行，有什么影响，而不是大眼瞪小眼。

#include<bits/stdc++.h>
using namespace std;
int n,T,rt,x,y,tot,a[100005],g[100005],cnt=0;
int dep[100005],fa[100005],val[100005],size[100005],sum[100005],son[100005],top[100005],id[100005]; 
int d[400005],la[400005];
bool vis[100005];
vector<int>v[100005];
void dfs1(int u,int from){
	fa[u]=from;
	size[u]=1;
	if(v[u].size()==1) sum[u]=1;
	dep[u]=dep[from]+1;
	int maxx=-1;
	for(int i=0;i<v[u].size();i++){
		int to=v[u][i];
		if(to!=from){
			dfs1(to,u);
			if(size[to]>maxx){
				maxx=size[to];
				son[u]=to;
			}
			size[u]+=size[to];
			sum[u]+=sum[to];
		}
	}
}
void dfs2(int u,int from,int utop){
	cnt++;
	id[u]=cnt;
	if(sum[u]%2==0) val[cnt]=1;
	top[u]=utop;
	if(son[u]) dfs2(son[u],u,utop); 
	for(int i=0;i<v[u].size();i++){
		int to=v[u][i];
		if(to!=from&&to!=son[u]){
			dfs2(to,u,to);
		}
	}
}
void push_down(int l,int r,int p,int mid){
	if(la[p]){
		d[p<<1]=(mid-l+1)-d[p<<1];
		d[p<<1|1]=(r-mid)-d[p<<1|1];
		la[p<<1]=!la[p<<1];
		la[p<<1|1]=!la[p<<1|1];
		la[p]=0;
	}
}
void push_up(int p){
	d[p]=d[p<<1]+d[p<<1|1];
}
void build(int l,int r,int p){
	if(l==r){
		d[p]=val[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	push_up(p);
}
void update(int l,int r,int p,int s,int t){
	if(l>=s&&r<=t){
		d[p]=(r-l+1)-d[p];
		la[p]=!la[p];
		return;
	}
	int mid=(l+r)>>1;
	push_down(l,r,p,mid);
	if(s<=mid) update(l,mid,p<<1,s,t);
	if(t>mid) update(mid+1,r,p<<1|1,s,t);
	push_up(p);
}
int getsum(int l,int r,int p,int s,int t){
	if(l>=s&&r<=t){
		return d[p];
	}
	int mid=(l+r)>>1,ans=0;
	push_down(l,r,p,mid);
	if(s<=mid) ans+=getsum(l,mid,p<<1,s,t);
	if(t>mid) ans+=getsum(mid+1,r,p<<1|1,s,t);
	return ans;
}
void update1(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,n,1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y); 
	update(1,n,1,id[x],id[y]);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>T;
	for(int i=1;i<=n-1;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(v[i].size()>=2){
			rt=i;
			break;
		}
	}
	dfs1(rt,0);
	dfs2(rt,0,rt);
	build(1,n,1);
	tot=sum[rt];
	while(T--){
		int leaf=0;
		cin>>x;
		for(int i=1;i<=x;i++){
			cin>>a[i];
			if(vis[a[i]]==false&&v[a[i]].size()==1) leaf++; 
			else{
				update1(rt,a[i]);
				g[i]=1;
			}
			vis[a[i]]=true;
		}
		if((tot+x-leaf)%2==1) cout<<"-1\n";
		else cout<<n+x-2+getsum(1,n,1,1,n)<<"\n"; 
		for(int i=1;i<=x;i++){
			if(g[i]==1){
				update1(rt,a[i]);
				g[i]=0;
			}
			vis[a[i]]=false;
		}
	}
	
	return 0;
}