CodeForces. 1339D Edge Weight Assignment

1.Problem.
https://codeforces.com/contest/1339/problem/D

2.Idea
Here

3.Source

 vector<int> adj[N];  
 int d[N];  
 set<int> st;  
 // calc dist from root  
 void dfs(int v, int p)  
 {  
      for (auto& x : adj[v]) {  
           if (x == p) continue;  
           d[x] = d[v] + 1;  
           dfs(x, v);  
      }  
 }  
 int main()  
 {  
      int n;  
      cin >> n;  
      for (int i = 1; i < n; i++) {  
           int v, u;  
           cin >> v >> u;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      int root = 0;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                root = i;  
                break;  
           }  
      }  
      dfs(root, 0);  
      int mn = 1, mx = n - 1;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                if (d[i] % 2 != 0) {  
                     mn = 3;  
                }  
                st.insert(adj[i][0]);  
                --mx;  
           }  
      }  
      mx += st.size();  
      cout << mn << " " << mx << endl;  
      return 0;  
 }