自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 22:24:09，当前版本为作者最后更新于2020-08-30 16:08:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的CEOI作战记录&题解-洛谷博客

我的CEOI作战记录&题解-cnblogs

考虑一个 $O(nq)$ 的暴力/结论:

首先,如果叶子节点数目为奇数,则必然无解,返回 $-1$.

随便选取一个度数 $>1$ 的点 $rt$ 为根进行dfs,然后考虑每个子树 $x(x\neq rt).$

记 $siz_x$ 为 $x$ 子树内的叶子节点个数,这个可以在dfs的过程中统计出.

如果 $siz_x$ 为奇数,那么 $x$ 到父亲的边至少要被清扫 $1$ 次.

如果 $siz_x$ 为偶数,那么 $x$ 到父亲的边至少要被清扫 $2$ 次.

证明:

可以发现这个问题是一个把所有叶子节点两两匹配并保证所有树上的边都被覆盖到的问题.

那么,每个子树 $x$ (除了根之外)必须要有至少一个叶子 $z$ ,它和子数外的另一个叶子进行匹配.

那么如果子树内的叶子数目是奇数,那么我就两两匹配然后留下 $1$ 个,否则我就两两匹配然后留下 $2$ 个.

因为所有非叶子节点度数 $>1$ ,并且每个子树往外匹配的叶子数目只有 $1$ 或 $2$ 个,所以一定可以成功匹配.

现在我们考虑优化.

答案为 总点数 $-$ $2$ $+$ $\sum\limits_{x∈T}[siz_x$ 是偶数 $]$

这个东西可以直接树剖维护, $O((\sum\limits_{i=1}^q D_i)\log^2 n).$

也可以用虚树做到 $O((n+ \sum\limits_{i=1}^q D_i)\log n).$

树剖做法代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
int n,rt,deg[N],size[N],fa[N],dpt[N],son[N],dval[N],suml; bool isl[N];
vector<int>G[N];
inline void dfs1(int x){
	size[x] = 1,dval[x] = 0; isl[x] = 1;
	for (int y,i = 0; i < G[x].size(); ++i) if ((y=G[x][i])^fa[x]){
		fa[y] = x,dfs1(y),size[x] += size[y],isl[x] = 0,dval[x] ^= dval[y];
		if (size[y] > size[son[x]]) son[x] = y; 
	}
	if (isl[x]) dval[x] = 1,++suml;
}
int top[N],id[N],pos[N],Time;
inline void dfs2(int x){
	id[x] = ++Time; pos[Time] = x;
	if (son[x]){
		top[son[x]] = top[x],dfs2(son[x]);
		for (int y,i = 0; i < G[x].size(); ++i) if (!top[y=G[x][i]]) top[y] = y,dfs2(y);
	}
}
int f0[N<<2],f1[N<<2]; bool rev[N<<2];
inline void up(int o){ f0[o] = f0[o<<1] + f0[o<<1|1],f1[o] = f1[o<<1] + f1[o<<1|1]; }
inline void Build(int o,int l,int r){
	rev[o] = f0[o] = f1[o] = 0;
	if (l == r){ if (dval[pos[l]]) f1[o] = 1; else f0[o] = 1; return; }
	int mid = l+r>>1; Build(o<<1,l,mid); Build(o<<1|1,mid+1,r); up(o); 
}
inline void Tag(int o){ rev[o] ^= 1,swap(f0[o],f1[o]); }
inline void down(int o){ if (rev[o]) Tag(o<<1),Tag(o<<1|1),rev[o] = 0; }
int ll,rr;
inline void Rev(int o,int l,int r){
	if (ll <= l && rr >= r){ Tag(o); return; }
	down(o); int mid = l+r>>1; if (ll <= mid) Rev(o<<1,l,mid); if (rr > mid) Rev(o<<1|1,mid+1,r); up(o);
}
inline void change(int l,int r){ if (l <= r) ll = l,rr = r,Rev(1,1,n); }
inline void work(int x){
	while (top[x] ^ rt) change(id[top[x]],id[x]),x = fa[top[x]]; change(id[rt],id[x]);
}
int opv[N],_,p[N],len;
int main(){
	int i,x,y,q; suml = 0;
	cin >> n >> q;
	for (i = 1; i < n; ++i)	cin >> x >> y,G[x].push_back(y),G[y].push_back(x),++deg[x],++deg[y];
	for (i = 1; i <= n; ++i) if (deg[i] > 1) rt = i;
	dfs1(rt),top[rt] = rt,dfs2(rt); Build(1,1,n);
	while (q--){
		cin >> len;
		for (i = 1; i <= len; ++i) cin >> p[i];
		sort(p+1,p+len+1);
		int cl = suml + len;
		for (_ = 0,i = 1; i <= len; ++i){
			if (opv[_] == p[i]) --_; else opv[++_] = p[i];
			if (p[i] != p[i-1] && isl[p[i]]){
				if (opv[_] == p[i]) --_; else opv[++_] = p[i]; --cl;
			}
		}
		for (i = 1; i <= _; ++i) work(opv[i]);
		cout << ((cl&1) ? -1 : len + n - 2 + f0[1]) << '\n';
		for (i = 1; i <= _; ++i) work(opv[i]);
	}
	return 0;
}