From any node P, we can visit at max two child of node P. The reason is , when we step into the node P the node is visited once, then lets say we went to a child A and came back from the child so we visited the node P twice. Now we can just visit another child and can not come back to the node P again, otherwise P will be visited more than twice.

Another important thing to notice is that when we go to visit the first child of P and willing to come back to P again we have to make sure that coming back to P does not require to visit any node more than twice. So we have to go through a straight path until we reach into a leaf node and come back to the P in the same path. In other words we will chose to visit only one child of each node until we reach into a leaf and then come back to P again by visiting some node twice. This way we can visit \(min(K , height[child])\) nodes.

It can be shown that before entering the 2nd child of P it is always better to spend as many K (double visit) as possible. Because when we enter the 2nd child of P we can not go back to P again and the tree shrinks for us.

Now come to the DP solution

lets say dp[i][j] = answer for the subtree of node-j when we have i nodes that can be visited twice.

transition : \(dp[i][j] = max(dp[i][j] , min(mxh,i) + dp[i-mxh][e] + 1)\) , for all i from 0 to K and for all edge e of node-j

\(mxh\) = maximum height of all the child except the child e

complexity : \(O(N*K)\)

c++ code: thakuremon

#include<bits/stdc++.h>
using namespace std;
vector<int> g[200005];
int height[200005] , dp[101][200005];
int n,k;

void dfs(int node,int par)
{
    height[node] = 0;
    for(int e:g[node])
    {
        if(e==par) continue;
        dfs(e,node);
    }
    int mx = 0;
    for(int e:g[node])
    {
        if(e==par) continue;
        mx = max(mx , height[e]);
    }
    height[node] = mx+1;
}

void dpontree(int node,int par)
{
    int mxh=0,mxh2=0;
    for(auto e:g[node])
    {
        if(e==par) continue;
        if(height[e] >= mxh)
        {
            mxh2 = mxh;
            mxh = height[e];
        }
        else if(height[e] > mxh2) mxh2 = height[e];
    }
    
    for(auto e:g[node])
    {
        if(e==par) continue;
        dpontree(e,node);
    }

    for(int i=0;i<=k;i++)
    {
        dp[i][node] = 1;
        for(auto e:g[node])
        {
            if(e==par) continue;
            if(height[e] == mxh)
            {
                dp[i][node] = max(dp[i][node] , min(mxh2,i) + dp[max(0,i-mxh2)][e] + 1);
            }
            else 
            {
                dp[i][node] = max(dp[i][node] , min(mxh,i) + dp[max(0,i-mxh)][e] + 1);
            }
        }
    }
}


int main()
{
    cin >> n >> k;
    for(int i=0;i<n-1;i++)
    {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    dpontree(1,0);
    cout << dp[k][1] << endl;
}