覆盖（cover）

你有 $n$ 个点的树，初始每一条边都没有颜色。

你有两种覆盖操作：

1. 选择 $u,v$ 满足 $u,v$ 路径上的边都没有颜色，然后将他们路径 $u,v$ 上的边都染色。
2. 选择 $u$ 满足 $u$ 的邻边都没有被染色，然后将 $u$ 的邻边染色。

要求用最少次数将所有边染色。

$n\le 10^5$。

首先你应该模拟大样例。

然后观察以 $x$ 为根的最优解结构：必然为如下两种状态：

1. 在这个点执行了邻边覆盖，那么这个点就会覆盖其父边。然后其就需要累加每一个儿子的答案，因为一个邻边覆盖会切断 $x$ 与儿子的联系。但是儿子的父边不能被覆盖。所以，我们至少应该设出关于 $x$ 的两个状态：$f_{x,0/1}$ 表示 $x$ 有/没有覆盖父边。那么只需要 $f_{x,0}\leftarrow f_{u,1}$。
2. 这个点不执行任何东西。那么他需要将儿子和连接儿子的边进行连接，然后转移。然后你就会发现这样一个结构：如果说 $x$ 有 $C$ 个儿子没有覆盖其父边，那么最优解肯定是让这 $C$ 个儿子两两配对。因此，这就涉及到奇偶性。

所以我们要这样设计：$f_{x,0/1/2}$ 表示 $x$ 为根的子树：

• $0$：有偶数个没有覆盖父边的儿子；
• $1$：有奇数个没有覆盖父边的儿子；
• $2$：自己覆盖了父边。

那么根据上面的分析，我们可以列出转移：

$$f_{x,2}\leftarrow \min\{f_{u,0},f_{u,1}\}$$

然后对于奇数和偶数，是差不多的。不妨只看奇数。

首先对于新的儿子 $u$，如果他覆盖了父边，那么 $u$ 和 $x$ 被切断了，完全独立。于是有：

$$f_{x,1}\leftarrow f_{x,1}+f_{u,2}$$

然后，如果 $u$ 没有覆盖父边，那么有两种情况：

1. $f_{u,1}$：这种情况下，$u$ 有一个额外伸出来没有匹配的树链，那么这个树链可以和 $u$ 到 $x$ 的边进行连接，一起覆盖，那么就有：$f_{x,1}\leftarrow f_{x,0}+f_{u,1}$；
2. $f_{u,0}$：这种情况下，$u$ 没有额外的树链，那么这个时候 $u$ 到 $x$ 的边单独成为一个树链。于是：$f_{x,1}\leftarrow f_{x,0}+f_{u,0}+1$。

然后就没了，$f_{x,0}$ 的转移是类似的，只要减去 $1$ 即可（因为可以和别的匹配）。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010,inf=1e9;
int n,f[N][3];
vector<int>v[N];
void dfs(int x,int fa){
    f[x][0]=f[x][1]=f[x][2]=inf;
    f[x][0]=0;f[x][2]=1;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        f[x][2]+=min(f[u][0],f[u][1]);
        int t0=f[x][0],t1=f[x][1];
        f[x][1]=min({t1+f[u][2],t0+f[u][1],t0+f[u][0]+1});
        f[x][0]=min({t0+f[u][2],t1+f[u][1]-1,t1+f[u][0]});
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1,x,y;i<n;i++){
        scanf("%lld%lld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    printf("%lld",min({f[1][0],f[1][1],f[1][2]}));
    return 0;
}