原题链接

题解

一开始我想的是每个节点要么建，要么不建，可是这样一来不好转移，因为有如下情况（黑色代表建站）

于是我们换一个角度思考，我们发现一个点要能通网，有三种情况：
1.自己建站
2.儿子建站
3.父亲建站

Code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
vector<ll> G[100005];
ll f[100005][4]={0};

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

void ss(ll now,ll fa)
{
    f[now][0]=0;
    f[now][1]=1;
    f[now][2]=0;
    ll add=2e17;
    for(auto next:G[now])
    {
        if(next==fa)continue;
        ss(next,now);
        add=min(add,f[next][1]-min(f[next][1],f[next][0]));
        f[now][0]+=min(f[next][1],f[next][0]);
        f[now][1]+=min(min(f[next][1],f[next][0]),f[next][2]);
        f[now][2]+=min(f[next][1],f[next][0]);//因为父亲建站可能会出现连环空，所以如果当前节点是空节点不能转移
    }
    f[now][0]+=add;
}

int main()
{
    ll n;
    read(n);
    for(ll i=1;i<n;i++)
    {
        ll x,y;
        read(x); read(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    ss(1,0);

    write(min(f[1][1],f[1][0]));
    putchar('\n');
    return 0;
}