Advertisement
mickypinata

TUMSO17: Network

Nov 22nd, 2021
769
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5.  
  6. vector<int> adj[N];
  7. int dp[N];
  8.  
  9. void DFS(int u, int p){
  10.     int mx = 0;
  11.     vector<int> tme;
  12.     for(int v : adj[u]){
  13.         if(v == p){
  14.             continue;
  15.         }
  16.         DFS(v, u);
  17.         tme.push_back(dp[v]);
  18.     }
  19.     sort(tme.begin(), tme.end(), greater<int>());
  20.     for(int i = 0; i < tme.size(); ++i){
  21.         mx = max(mx, tme[i] + i + 1);
  22.     }
  23.     dp[u] = mx;
  24. }
  25.  
  26. int main(){
  27.  
  28.     int nVertex, rt;
  29.     scanf("%d%d", &nVertex, &rt);
  30.     for(int i = 1; i < nVertex; ++i){
  31.         int u, v;
  32.         scanf("%d%d", &u, &v);
  33.         adj[u].push_back(v);
  34.         adj[v].push_back(u);
  35.     }
  36.     DFS(rt, 0);
  37.     cout << dp[rt];
  38.  
  39.     return 0;
  40. }
  41.  
Advertisement
RAW Paste Data Copied
Advertisement