给定一棵以 $1$ 为根的树，初始每个点都没被点亮，每个时刻可以改变一个点的点亮状态，需要让每个点 $u$ 都在某个时刻满足”有且仅有 $u$ 的子树被点亮“，最终所有点都没被点亮。求至少经过多少时刻。

$n\leq 2\times 10^5$。

转化一下题意：记 $sz_u$ 为 $u$ 子树大小。对于一条树边 $(u,fa_u)$，在新图 $G$ 上添加 $u,fa_u$ 之间权值为 $sz_{fa_u}-sz_u$ 的双向边；对于一个点 $u$，在 $G$ 上添加 $u$ 和新点 $S$ 之间权值为 $sz_u$ 的边。则原问题等价于找到一个边的多重集，满足：

• $1\sim n$ 中的每个点度数都 $>0$ 且为偶数。
• $1\sim n$ 连通。

如果满足这两个条件，就可以构造出一组 $S$ 出发的欧拉回路，其中 $S$ 表示没有任何点点亮的状态，$u$ 表示仅 $u$ 子树点亮的状态，则显然是充要条件。每条边只会被加入多重集 $0,1$ 或 $2$ 次，更多次显然是不优的。设计一个树形 dp $f_{u,0/1,0/1}$ 表示 $u$ 子树是否满足以下条件的最小花费：

• 根节点是否与 $S$ 连通。需要保证所有不与根节点连通的结点都与 $S$ 连通。
• 根节点的度数是否是奇数。

转移先考虑第一维。有 $f_{u,0,0}=0,f_{u,1,1}=w,f_{u,1,0}=2w$。其实是 $(u,S)$ 边的选择次数，所以 $w=sz_u$。

然后合并 $u$ 连通块和儿子 $v$ 子树，其中 $w$ 代表 $G$ 中 $(u,v)$ 的权值：

• $(u,v)$ 选 $0$ 次。$f_{u,i,j}+f_{v,1,0}\to f'_{u,i,j}$。
• $(u,v)$ 选 $1$ 次。$f_{u,i,j}+f_{v,i',1}+w\to f'_{u,i\operatorname{or} i',j\operatorname{xor} 1}$。
• $(u,v)$ 选 $2$ 次。$f_{u,i,j}+f_{v,i',0}+2w\to f'_{u,i\operatorname{or} i',j}$。

wow，居然 $O(n)$ 了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=2e5+5,INF=1e9;
int n,siz[N];
ll f[N][3];
vector<int> G[N];
void dfs(int x){
	siz[x]=1;
	for(auto &y:G[x])
		dfs(y),
        siz[x]+=siz[y];

	f[x][0]=0,f[x][1]=siz[x],f[x][2]=siz[x]<<1;
	for(auto &y:G[x]){
		int z=siz[x]-siz[y];
		f[x][2]=min({f[x][2]+f[y][0]+(z<<1),f[x][0]+f[y][2]+(z<<1),f[x][1]+f[y][1]+z,f[x][2]+f[y][2]});
		f[x][1]=min({f[x][1]+f[y][0]+(z<<1),f[x][0]+f[y][1]+z,f[x][1]+f[y][2]});
		f[x][0]=min({f[x][0]+f[y][0]+(z<<1),f[x][0]+f[y][2]});
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2,x;i<=n;i++){
		scanf("%d",&x);
        G[x].emplace_back(i);
	}
	dfs(1);
	printf("%lld\n",f[1][2]);
	return 0;
}