Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. typedef long long int ll;
  5.  
  6. const int MX=100005;
  7. bool notroot[MX];
  8. vector<int> children[MX];
  9. ll sigma_height=0;
  10. int dfs(int now,int d=-1){
  11.     if(children[now].size()==0)return 0;
  12.     int mxh=0;
  13.     for(int to:children[now]){
  14.         int h=dfs(to,d+1);
  15.         mxh=max(mxh,h);
  16.     }
  17.     mxh++;
  18.     sigma_height+=mxh;
  19.     return mxh;
  20. }
  21. int main(void){
  22.     ios::sync_with_stdio(false);
  23.     int n;
  24.     cin>>n;
  25.     for(int i=1;i<=n;i++){
  26.         int k,a;
  27.         cin>>k;
  28.         for(int j=0;j<k;j++){
  29.             cin>>a;
  30.             notroot[a]=true;
  31.             children[i].push_back(a);
  32.         }
  33.     }
  34.     int root=0;
  35.     for(int i=1;i<=n;i++){
  36.         if(!notroot[i]){
  37.             root=i;
  38.             break;
  39.         }
  40.     }
  41.     dfs(root);
  42.     cout<<root<<'\n'<<sigma_height<<'\n';
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement