<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

280. Trade centers
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Thecountry has N cities connected by N-1 bidirectional roads; one can travel from any city to any other by the roads. One of the biggest trade networksis going to build in some cities trade centers selling the main national product. Because building each trade center costs the company a lot of money, they want to build as few of them as possible. Becauseis the biggest producer of the main national product, a citizen living in each city must be able to reach some supermarket using at most K roads.

Your task is to determine where to build the trade centers.

Input
The first line of the input contains two integers N and K (1≤ N≤ 30000, 1≤ K≤ 100). Each of the next N-1 lines contains two integers, denoting the numbers of the cities connected by a road. The cities are numbered starting from 1.

Output
Output the number of the trade centers followed by the numbers of the cities where the trade centers should be built.

Example(s)
sample input
sample output
4 1
1 2
2 3
4 2
1
2



Novosibirsk SU Contest #2, by Novosibirsk Team #1

<|response|>
1. Abridged problem statement  
Given an undirected tree of N cities (nodes) and an integer K, place as few “trade centers” (selected nodes) as possible so that every city is at distance at most K from at least one center. Output the number of centers and their labels.

2. Key observations  
- We can root the tree arbitrarily (say at city 1) and do a single post-order DFS.  
- Define dp[u] = the distance from u down to the nearest center already placed in u’s subtree.  
- For a leaf u (no children), we initialize dp[u] = K+1, meaning “no center in its subtree yet, at distance K+1.”  
- When processing an internal node u, we gather all child dp[v] values into a list. Let mn = min(dp[v]) and mx = max(dp[v]).  
  - If mn + mx + 2 ≤ 2K+1, then the closest subtree (mn) can cover u and still remain within distance K of the farthest subtree, so we set dp[u] = mn+1.  
  - Otherwise, the farthest uncovered subtree would form a path of length ≥ 2K+2 with some other uncovered subtree if we don’t intervene, so we “carry up” the farthest branch by setting dp[u] = mx+1.  
- Whenever dp[u] reaches exactly 2K+1, it means we are forced to place a center at u (otherwise some leaf‐to‐leaf distance would exceed 2K). We then record u as a center and reset dp[u] = 0.  
- After DFS, if dp[root] > K, the root itself is still too far from any center, so we add it.  
- Finally, sort and output the list of centers.  
This greedy is optimal because we only place a center when a “critical” path would otherwise exceed length 2K.

3. Full solution approach  
a. Read N, K and the N−1 edges into an adjacency list.  
b. Prepare an array dp[1..N] and an empty list centers.  
c. Define a recursive DFS(u, parent):  
   - For each child v ≠ parent, call DFS(v,u). Collect dp[v] into a vector child_dp.  
   - If child_dp is empty, set dp[u] = K+1.  
   - Otherwise let mn = min(child_dp), mx = max(child_dp).  
        • If mn + mx + 2 ≤ 2K+1, dp[u] = mn+1.  
        • Else dp[u] = mx+1.  
   - If dp[u] == 2K+1, place a center: dp[u]=0 and centers.push_back(u).  
d. Call DFS(1,0). If dp[1] > K, append 1 to centers.  
e. Sort centers, print centers.size() then each center on its own line.

4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

int N, K;
vector<vector<int>> adj;
vector<int> dp;          // dp[u] = distance from u to nearest center in its subtree
vector<int> centers;

void dfs(int u, int parent) {
    vector<int> child_dp;
    // Process all children
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        child_dp.push_back(dp[v]);
    }
    if (child_dp.empty()) {
        // Leaf: no center below it yet → pretend at distance K+1
        dp[u] = K + 1;
    } else {
        int mn = *min_element(child_dp.begin(), child_dp.end());
        int mx = *max_element(child_dp.begin(), child_dp.end());
        // Decide which branch to carry upward
        if (mn + mx + 2 <= 2 * K + 1) {
            dp[u] = mn + 1;
        } else {
            dp[u] = mx + 1;
        }
    }
    // If dp[u] hits the threshold 2K+1, place a center at u
    if (dp[u] == 2 * K + 1) {
        dp[u] = 0;
        centers.push_back(u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;
    adj.assign(N+1, {});
    dp.assign(N+1, 0);

    // Read edges
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Run DFS from node 1
    dfs(1, 0);

    // If root remains too far from any center, add it
    if (dp[1] > K) {
        centers.push_back(1);
    }

    sort(centers.begin(), centers.end());
    cout << centers.size() << "\n";
    for (int c : centers) {
        cout << c << "\n";
    }
    return 0;
}
```

5. Python implementation with detailed comments

```python
import sys
sys.setrecursionlimit(10**7)

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    K = int(next(it))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u = int(next(it)); v = int(next(it))
        adj[u].append(v)
        adj[v].append(u)

    dp = [0] * (N+1)
    centers = []

    def dfs(u, parent):
        child_dp = []
        for v in adj[u]:
            if v == parent:
                continue
            dfs(v, u)
            child_dp.append(dp[v])
        if not child_dp:
            # Leaf: no center below → pretend at distance K+1
            dp[u] = K + 1
        else:
            mn = min(child_dp)
            mx = max(child_dp)
            # If the closest + farthest + 2 ≤ 2K+1, we can carry mn
            if mn + mx + 2 <= 2*K + 1:
                dp[u] = mn + 1
            else:
                dp[u] = mx + 1
        # If we hit dp[u] == 2K+1, place a center here
        if dp[u] == 2*K + 1:
            dp[u] = 0
            centers.append(u)

    dfs(1, 0)
    # If root still > K from any center, add it
    if dp[1] > K:
        centers.append(1)

    centers.sort()
    print(len(centers))
    for c in centers:
        print(c)

if __name__ == "__main__":
    main()
```

Explanation of complexity: Each node is visited once and its children’s dp values are processed in O(deg(u)). Total time O(N), which is efficient for N up to 30000.