Tree with Small Distances

题意：
给你一颗有n个节点的无向树，你可以往树中加无向边，求你形成1节点到任意一个节点距离小于等于2的图加边的最小次数？

思路：
你可以认为是求一个变形的最小支配集，即求以1节点为根节点时第0，1，2层无需考虑的最小支配集，所以可以用动态规划和贪心算法解决。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> g[300005];
const ll inf=1000000007;
int dp[300005][3], ans=0;

void dfs(int v,int d,int f)
{
    if(f!=-1&&g[v].size()==1)
    {
        if(d<=2)
        {
            dp[v][0]=1;
            dp[v][1]=0;
            dp[v][2]=0;
        }
        else
        {
            dp[v][0]=1;
            dp[v][1]=inf;
            dp[v][2]=0;
        }
        return ;
    }
    dp[v][0]=1;
    dp[v][2]=0;
    int flag=0, mi=inf;
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i]!=f)
        {
            dfs(g[v][i],d+1,v);
            if(d<=2)
            {
                dp[v][0]+=min(min(dp[g[v][i]][0],dp[g[v][i]][1]),dp[g[v][i]][2]);
                dp[v][1]+=min(dp[g[v][i]][0],dp[g[v][i]][1]);
                dp[v][2]+=min(dp[g[v][i]][0],dp[g[v][i]][1]);
                flag=1;
            }
            else
            {
                dp[v][0]+=min(min(dp[g[v][i]][0],dp[g[v][i]][1]),dp[g[v][i]][2]);
                dp[v][1]+=min(dp[g[v][i]][0],dp[g[v][i]][1]);
                dp[v][2]+=min(dp[g[v][i]][0],dp[g[v][i]][1]);
                mi=min(mi,abs(dp[g[v][i]][0]-dp[g[v][i]][1]));
                if(dp[g[v][i]][0]<=dp[g[v][i]][1])
                {
                    flag=1;
                }
            }
        }
    }
    if(flag==0)
    {
        dp[v][1]+=mi;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n-1; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0,-1);
    cout << min(dp[1][0],dp[1][1]) << endl;
    return 0;
}