题目大意

给出一个 $n$ 个节点的树，初始时你在节点 $1$，你需要将每一个节点至少遍历一次（可以重复经过），求最小所需时间。
对于给出的树上边，经过这些边花费一个单位时间
除此之外，你可以从任意节点不消耗任何时间直接传送到 $1$ 号节点，并且该操作可以使用无限次。
求将该树按要求遍历至少需要多少单位时间

解题思路

这题据说是一道很套路的树形DP，虽然我没见过

设 $f_{x,0}$ 表示将 $x$ 的子树遍历并且回到 $x$ 所需要的最少时间
$f_{x,1}$ 表示将 $x$ 的子树遍历并且不回到 $x$ 所需要的最少时间

那么转移应该很显然：
PS：$d$ 表示深度，根节点的深度为 $1$
$f_{x,0}=\sum\limits_y \min(f_{y,0}+2,f_{y,1}+d_x)$
两种情况分别为从 $y$ 回到 $x$ 和 从根节点回到 $x$
$f_{x,1}=f_{x,0}-\max\limits_{y}\{\min(f_{y,0}+2,f_{y,1}+d_x)-(f_{y,1}+1)\}$
显然只能选择一个子节点的子树不回来，则选不回来省时间最多的那个

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=1000000+10;
const int Maxm=Maxn<<1;
const int inf=0x3f3f3f3f;
int head[Maxn],f[Maxn][2];
int nxt[Maxm],to[Maxm],d[Maxn];
int n,edgecnt;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
inline void add(int x,int y)
{
    ++edgecnt;
    nxt[edgecnt]=head[x];
    to[edgecnt]=y;
    head[x]=edgecnt;
}
void dfs(int x,int fa)
{
    d[x]=d[fa]+1;
    int tmp=-inf;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==fa)continue;
        dfs(y,x);
        f[x][0]+=min(f[y][0]+2,f[y][1]+d[x]);
        tmp=max(tmp,min(f[y][0]+2,f[y][1]+d[x])-(f[y][1]+1));
    }
    if(tmp==-inf)f[x][1]=0;
    else f[x][1]=f[x][0]-tmp;
}
int main()
{
//    freopen("in.txt","r",stdin);
    n=read();
    for(int i=2;i<=n;++i)
    {
        int x=read();
        add(x,i),add(i,x);
    }
    dfs(1,0);
    printf("%d\n",min(f[1][1],f[1][0]));
    return 0;
}