P2899 [USACO08JAN]Cell Phone Network G

树形DP。
思路参考题解。

典型的树形$DP$

不妨设$f[x][0]$为x节点被自己影响，$f[x][1]$为被儿子影响，$f[x][2]$为被父亲影响

显然，

$f[x][0]=sum(min(f[son][0],f[son][1],f[son][2]))$

$f[x][2]=sum(min(f[son][0],f[son][1]))$

而$f[x][1]$，即被自己的儿子影响，只要x所有的儿子中有一个放了信号塔就ok了，其余的儿子放不放无所谓

那么我们可以枚举这个儿子是谁

假设这个儿子是$sn$，除$sn$以外的儿子是$u$

那么最终$f[x][1]=f[sn][0]+min(f[u][1],f[u][0]) $$//$其中$u$儿子可以参照$f[x][2]$

看题解吧写的好多了$qwq$

细节见代码.

#include <bits/stdc++.h>
#define ll long long
#define maxn 10001
using namespace std;
ll n,u,v,hd[maxn],ct,fa[maxn],f[maxn][3];
struct Node{
    ll to,nx;
}e[maxn<<2];
inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
inline void add(ll x,ll y){
    e[++ct].to=y;
    e[ct].nx=hd[x];
    hd[x]=ct;
}
inline void dfs(ll x){
    ll sn=0;
    f[x][0]=1;
    for(register int i=hd[x];i;i=e[i].nx){
        ll u=e[i].to;
        if(u!=fa[x]){
            fa[u]=x;
            dfs(u);
            f[x][0]+=min(f[u][0],min(f[u][1],f[u][2]));
            f[x][2]+=min(f[u][0],f[u][1]);
            if((f[sn][0]-min(f[sn][0],f[sn][1]))>(f[u][0]-min(f[u][0],f[u][1])))
                sn=u;
        }
    }
    f[x][1]=f[sn][0];
    for(register int i=hd[x];i;i=e[i].nx){
        ll u=e[i].to;
        if(fa[x]==u||sn==u)        continue;
        f[x][1]+=min(f[u][0],f[u][1]);
    }
}
int main(){
    n=read();
    for(register int i=1;i<n;++i){
        u=read();v=read();
        add(u,v);add(v,u);
    }
    f[0][0]=0x3f3f3f3f;
    dfs(1);
    printf("%lld\n",min(f[1][0],f[1][1]));
    return 0;
}