【题目描述】：
    比特镇一共有n个房子，编号依次为1到n，这些房子通过n-1条无向道路连通在一起，形成了一棵树的结构。
    Bytesear要在比特镇实施Wifi搭建计划，他要让Wifi覆盖到比特镇的每一条道路。
    Bytesear可以安置无限多个Wifi发射器，但是只能安置在树上的节点上，一个房子可以安置多个Wifi发射器。
    对于一条道路(a,b)，如果它满足以下两个条件之中的至少一个，那么这条边将被Wifi覆盖：
    1.a点放置了Wifi发射器或者和b点放置了Wifi发射器。
    2.与a点或b点直接相邻的点中，至少放置了两个Wifi发射器。
    请帮助Bytesear规划一个最优的放置方案，使得Wifi覆盖到比特镇的每一条道路，且放置的Wifi发射器总数尽可能少。
【题目解法】：
    f[i][j]表示i号节点不放无线电儿子节点放了j个且不需要父亲节点放的最小代价
    g[i][j]表示i号节点不放无线电需要父亲节点放j个的最小代价
    h[i][j]表示i号节点放j个无线电且不需要父亲节点放的最小代价
    ans[i]表示覆盖以i为根的子树的最小代价
    注意f[i][j]中j最多枚举到2即可，大于2都可以默认为2，因为大于2和等于2对转移没有影响
    然后一个节点最多放2个，放多了和放2个没有区别
    然后我们一个个转移
    ans[i]=min(f[i][0],f[i][1],f[i][2],h[i][1],h[i][2])
    考虑f的转移
    1.f[i][0] 那么需要每个儿子从自己的儿子中获得两个无线电，即sigma(f[son][2])
    2.f[i][1] 那么枚举哪个儿子被选中，那个儿子的贡献就是h[son][1]，其他的儿子的贡献是sigma(f[son][1])
    3.f[i][2] 我们令F[i][j]表示前i个儿子有j个放了无线电F[i][j]+h[son][1]->F[i+1][j+1] F[i][j]+ans[son]->F[i+1][j]
    考虑g的转移
    1.g[i][1]
      要么由一个儿子覆盖一个，其他的不需要 那么就是h[Son][1]+sigma(ans[son])
      要么所有儿子都不放，由儿子的儿子提供 那么就是sigma(f[son][1])
    2.g[i][2]=sigma(ans[son])
    考虑h的转移
    1.h[i][1]=sigma(min(ans[son],g[son][1]))+1
    2.h[i][2]=sigma(min(ans[son],g[son][2]))+2
    最后注意一下覆盖一下
    即g[i][j]=min(g[i][j],g[i][j-1])
      h[i][j]=min(h[i][j],h[i][j+1])
      f[i][j]=min(f[i][j],f[i][j+1])
    复杂度O(N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=200005;
const int M=400005;
struct edge {int x,next;} b[M];
int n,tot,a[N],into[N],c[N],INF;
int f[N][3],g[N][3],h[N][3],F[N][3],ans[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void addedge(int x,int y)
{
    ++tot;
    b[tot].x=y;
    b[tot].next=a[x];
    a[x]=tot;
}
void init()
{
    n=getint(); into[1]=n;
    for (int i=1; i<n; i++)
    {
        int x=getint(),y=getint();
        addedge(x,y); addedge(y,x);
        into[x]++; into[y]++;
    }
    memset(f,127,sizeof(f));
    memset(g,127,sizeof(g));
    memset(h,127,sizeof(h));
    memset(ans,127,sizeof(ans));
    INF=ans[0];
}
inline void add(int &a,int b)
{
    if (a>=INF) return;
    if (b>=INF) {a=INF; return;}
    a+=b;
}
void dfs(int x,int fa)
{
    if (into[x]==1)
    {
        f[x][0]=0; g[x][1]=g[x][2]=0;
        h[x][1]=1; h[x][2]=2; ans[x]=0; return;
    }
    for (int p=a[x];p;p=b[p].next) if (b[p].x!=fa) dfs(b[p].x,x); int cnt=0;
    for (int p=a[x];p;p=b[p].next) if (b[p].x!=fa) c[++cnt]=b[p].x;
    f[x][0]=0; for (int i=1; i<=cnt; i++) add(f[x][0],f[c[i]][2]);
    int sum=0; for (int i=1; i<=cnt; i++) add(sum,min(f[c[i]][1],f[c[i]][2]));
    int num=0; for (int i=1; i<=cnt; i++) if (min(f[c[i]][1],f[c[i]][2])==INF) num++;
    if (sum!=INF) for (int i=1; i<=cnt; i++) f[x][1]=min(f[x][1],sum-min(f[c[i]][1],f[c[i]][2])+min(h[c[i]][1],h[c[i]][2]));
    if (num==1)
    {
        for (int i=1; i<=cnt; i++) if (min(f[c[i]][1],f[c[i]][2])==INF) num=i; f[x][1]=0;
        for (int i=1; i<=cnt; i++) add(f[x][1],(num==i)?min(h[c[i]][1],h[c[i]][2]):min(f[c[i]][1],f[c[i]][2]));
    }
    for (int i=0; i<=cnt; i++) F[i][0]=F[i][1]=F[i][2]=INF; F[0][0]=0;
    for (int i=0; i<cnt; i++)
        for (int j=0; j<=2; j++)
        {
            if (F[i][j]==INF) continue;
            F[i+1][j]=min(F[i+1][j],F[i][j]+ans[c[i+1]]);
            F[i+1][min(j+1,2)]=min(F[i+1][min(j+1,2)],F[i][j]+min(h[c[i+1]][1],h[c[i+1]][2]));
            F[i+1][min(j+2,2)]=min(F[i+1][min(j+2,2)],F[i][j]+h[c[i+1]][2]);
        }
    f[x][2]=F[cnt][2];
    sum=0; for (int i=1; i<=cnt; i++) add(sum,ans[c[i]]); g[x][2]=min(g[x][2],sum);
    for (int i=1; i<=cnt; i++) g[x][1]=min(g[x][1],sum-ans[c[i]]+min(h[c[i]][1],h[c[i]][2]));
    sum=0; for (int i=1; i<=cnt; i++) add(sum,min(f[c[i]][1],f[c[i]][2])); g[x][1]=min(g[x][1],sum);
    h[x][1]=1; for (int i=1; i<=cnt; i++) add(h[x][1],min(ans[c[i]],g[c[i]][1]));
    h[x][2]=2; for (int i=1; i<=cnt; i++) add(h[x][2],min(ans[c[i]],min(g[c[i]][2],g[c[i]][1])));
    for (int i=0; i<=2; i++) ans[x]=min(ans[x],min(f[x][i],h[x][i]));
}
int main()
{
    init();
    dfs(1,0);
    printf("%d\n",ans[1]);
    return 0;
}