这种问题一看满足条件就知道，一般不用想着怎么模拟题意。考虑转化问题。
假如节点 \(u\) 满足了条件一，也就是仅有子树节点全部开启。那么我们把转化具象为：
- 进行 \(\text{siz}_u\) 次操作直接清空；
- 进行 \(\text{siz}_{\text{fa}(u)}-\text{siz}_u\) 次操作使 \(\text{fa}(u)\) 满足条件一；
- 对于任意 \(v\in\text{son}_u\)，进行 \(\text{siz}_u-\text{siz}_v\) 次操作使 \(v\) 满足条件一；
发现我们关注的条件只有：
- 清空状态和全满状态的转化；
- 两棵子树之间的转化。
于是考虑转化问题为：建新图，对于原图中任意的 \((u,\text{fa}(u))\) 的边，添加两条 \(\{u,\text{fa}(u),\text{siz}_{\text{fa}(u)}-\text{siz}_u\}\) 的双向边。然后对于任意一点 \(u\)，添加两条 \(\{0,u,\text{siz}_u\}\) 的双向边。然后问题转化为在新图找一个点数为原图点数且边权最小的欧拉子图。
这个欧拉子图找出来之后，我们发现：若删去 \(0\) 点，则这个欧拉子图形成了若干连通块，每个连通块都恰好有 \(2\) 条边与 \(0\) 点相连。
然后设计 DP 方程为：设 \(f_{u,0/1/2}\) 表示以 \(u\) 为根的子树，删掉 \(0\) 后有 \(0/1/2\) 条边满足一端是 \(0\)、另一端属于这个子树的最小花费。初始状态 \(f_{u,0}=0\)，\(f_{u,1}=\text{siz}_u\)，\(f_{u,2}=2\,\text{siz}_u\)。
注意方程第二维为 \(0/1\) 的情况，可以类比为当前点是连通块的一端；对于 \(2\) 的情况，则就是上文说的恰好 \(2\) 条边和 \(0\) 相连的情况。
令 \(v\in\text{son}_u\)，\(w=\text{siz}_u-\text{siz}_v\)。有转移：
\[f_{u,0}\gets\min(f_{u,0}+f_{v,0}+2w,f_{u,0}+f_{v,2}) \]可以理解为要么 \(v\) 要转移到 \(u\)，这两个状态转移需要 \(2w\) 的花费；要么 \(v\) 已经是一个欧拉图，把 \(u\) 接入 \(v\) 的花费。
\[\begin{matrix} f_{u,1}\gets\min(f_{u,1}+f_{v,0}+2w,f_{u,0}+f_{v,1}+w,f_{u,1}+f_{v,2})\\[1ex] f_{u,2}\gets\min(f_{u,0}+f_{v,2}+2w,f_{u,2}+f_{v,0}+2w,f_{u,1}+f_{v,1}+w,f_{u,2}+f_{v,2}) \end{matrix} \]和上面是同理的。
最后答案就是 \(f_{1,2}\)。复杂度做到了 \(O(n)\)。
#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
char buf[1<<20],*p1=buf,*p2=buf;
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))ch=='-'&&(f=-1),ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
constexpr int MAXN=2e5+5;
int n,head[MAXN],tot;
struct{
int v,to;
}e[MAXN];
void addedge(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
int siz[MAXN],f[MAXN][3];
void dfs(int u){
siz[u]=1;
for(int i=head[u];i;i=e[i].to) dfs(e[i].v),siz[u]+=siz[e[i].v];
f[u][0]=0,f[u][1]=siz[u],f[u][2]=siz[u]<<1;
for(int i=head[u],v,w,t0,t1,t2;i;i=e[i].to){
v=e[i].v,w=siz[u]-siz[v];
t0=min(f[u][0]+f[v][0]+2*w,f[u][0]+f[v][2]);
t1=min({f[u][1]+f[v][0]+2*w,f[u][0]+f[v][1]+w,f[u][1]+f[v][2]});
t2=min({f[u][2]+f[v][0]+2*w,f[u][0]+f[v][2]+2*w,f[u][1]+f[v][1]+w,f[u][2]+f[v][2]});
f[u][0]=t0,f[u][1]=t1,f[u][2]=t2;
}
}
int main(){
n=read();
for(int i=2;i<=n;++i) addedge(read(),i);
dfs(1);
printf("%d\n",f[1][2]);
return 0;
}