树上问题模板

· · 个人记录

最小边覆盖问题

void dp(int u,int fa)
{   
    f[u][1]=1;
    f[u][0]=0;
    for(int i=First[u];i;i=Next[i])
    {
        int v=go[i];
        if(v==fa) continue;
        dp(v,u);
        f[u][0]+=f[v][1];
        f[u][1]+=min(f[v][1],f[v][0]);
    }
    res=min(f[1][1],f[1][0]);
}

最小点覆盖问题

inline void dfs(int u,int fa)
{
    for(int i=First[u];i;i=Next[i])
    {
        int v=go[i];
        if(v==fa) continue;
        dfs(v,u);
        rep[u]=max(rep[u],rep[v]+1);
        sum[u]=max(sum[u],sum[v]-1);
    }

    rep[u]=max(rep[u],0);
    if(sum[u]>=rep[u]) rep[u]=-1;
    if(rep[u]==k)
    {
        sum[u]=k;
        rep[u]=-1;
        ans++;
    }
}

int main( )
{
    scanf("%d%d%d",&n,&k,&t);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    memset(rep,-1,sizeof(rep));
    memset(sum,-1,sizeof(sum));
    dfs(1,0);
    if(sum[1]>=rep[1]) rep[1]=-1;
    if(rep[1]!=-1) ans++;
    printf("%d\n",ans);
    return 0;
}

树的直径

void dp(int u,int fa)
{   
    for(int i=First[u];i;i=Next[i])
    {
        int v=go[i];
        if(v==fa) continue;
        dp(v,u);
        res=max(res,ans[u]+ans[v]+w[i]);
        ans[u]=max(ans[u],ans[v]+w[i]);
    }
}