题解 P5969【POI2016 Nadajniki】

· · 题解

树形 dp。

思考转移的时候可以考虑开始只有一个点，每次加一棵子树进去，这样思考起来会清晰一点。

由于覆盖一条边的可能是相邻点或者其相邻边连向的点，所以处理时 i 子树内与 i 相邻的边可能未被覆盖，所以需要将其考虑到状态里。

记 f_{i,j=0/1/2/3/4,k=0/1/2} 表示 i 子树内，j=0 表示 i 与 i 的儿子都没有放发射器，j=1/2 分别表示 i 放了 1、2 个发射器，j=3/4 分别表示 i 的儿子放了 1、\geq2 个发射器，k 表示 i 子树内与其相邻的边还需要的发射器数量。

不需要考虑 i 和 i 儿子都放了发射器的情况，因为这个时候只有 i 上的发射器有用。

转移时，记当前节点为 u，加入的儿子为 v。

先考虑 v 子树内与 v 相邻的未覆盖边，它们需要 u 放的发射器数量为 v 状态中的 k，根据这个条件先判掉不合法的转移。

再考虑 u 与 v 之间的连边：

  1. 如果 u 或 v 上有发射器，则此边已被覆盖，直接不管；

  2. 否则此边相邻点上的发射器数量为 u 儿子上发射器数量 + v 儿子上发射器数量，这两个都记在 dp 状态中了。根据这个更新 u 状态的 k 值。

还有就是根据 v 上的发射器数量来更新 u 状态 j,k 的值。

具体可以自己画张图思考一下，或者直接看代码

\texttt{Code Below} 
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int inf;

int read()
{
    int s=0;
    char c=getchar(),lc='+';
    while (c<'0'||'9'<c) lc=c,c=getchar();
    while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
    return lc=='-'?-s:s;
}
void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
void print(int x,char c='\n')
{
    write(x);
    putchar(c);
}
struct edge
{
    int to,nxt;
}e[N*2];
int head[N],cnte=0;
void add_edge(int u,int v)
{
    e[++cnte].to=v;
    e[cnte].nxt=head[u];
    head[u]=cnte;
}
int f[N][5][3],g[5][3];
bool trans(int x,int y,int a,int b,int &c,int &d)
{
    c=x,d=y;
    if (b)
    {
        if (x>2) return 0;
        if (x<b) return 0;
    }
    if (1<=a&&a<=2) d=max(d-a,0);
    if (!((1<=a&&a<=2)||(1<=x&&x<=2)))
    {
        int tot=max(a-2,0)+max(x-2,0);
        d=max(d,2-tot);
    }
    if (1<=a&&a<=2&&!(1<=c&&c<=2)) c=min(a+max(c-2,0)+2,4);
    return 1;
}
void dfs(int now,int father)
{
    f[now][0][0]=0;
    f[now][1][0]=1;
    f[now][2][0]=2;
    for (int i=head[now];i;i=e[i].nxt)
    {
        int to=e[i].to,c,d;
        if (to==father) continue;
        dfs(to,now);
        memcpy(g,f[now],sizeof(g));
        memset(f[now],0x3f,sizeof(f[now]));
        for (int x=0;x<=4;x++)
        for (int y=0;y<=2;y++)
        if (g[x][y]<inf)
        for (int a=0;a<=4;a++)
        for (int b=0;b<=2;b++)
        if (f[to][a][b]<inf)
        if (trans(x,y,a,b,c,d))
        f[now][c][d]=min(f[now][c][d],g[x][y]+f[to][a][b]);
    }
}

signed main(signed bangumi,char *ss969[])
{
    (void)bangumi,(void)ss969;
    memset(f,0x3f,sizeof(f));
    inf=f[0][0][0];
    int n=read();
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,0);
    int ans=inf;
    for (int i=0;i<=4;i++) ans=min(ans,f[1][i][0]);
    print(ans);

    return 0;
}