1029E.Tree with Small Distances(经典树dp)

传送门

观察发现一定是从 $1$ 连出来的边最划算

而且连到一个点之后,这个点周围的所有点都是满足要求的.

定义 $f[u][1]$ 为和 $1$ 有连边

$f[u][2]$ 为通过父亲到 $1$

$f[u][3]$ 为通过儿子到 $1$

那么 $f[u][1]=\sum\limits_{v}min(f[v][1],f[v][2],f[v][3])$

那么 $f[u][2]=\sum\limits_vmin(f[v][1],f[v][3])$

$f[u][3]=f[u][2]$

但是如果 $u$ 的儿子没有一个和 $1$ 有边,还需要选一个儿子和 $1$ 相连...

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v)
{
    d[++cnt]=(edge){v,head[u]},head[u] = cnt;
}
int n,f[maxn][3],ans;
//1表示直接相连
//2表示经过父亲再到自己
//3表示经过儿子再到自己 
void dfs(int u,int fa,int dep)
{
    if( dep>=2 )    f[u][1] =1;
    int minn = 1e9;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==fa )    continue;
        dfs(v,u,dep+1);
        f[u][1] += min( {f[v][1],f[v][2],f[v][3]} );
        f[u][2] += min( f[v][1],f[v][3] );
        minn = min( minn,f[v][1]-f[v][3] );
    }
    f[u][3] = f[u][2]+max(0,minn);
}
int main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int l,r; cin >> l >> r;
        add(l,r); add(r,l);
    }
    dfs(1,0,0);
    for(int i=head[1];i;i=d[i].nxt )
        ans += f[d[i].to][1];
    cout << ans;
}