fork download
copy 
  1. #include <map>
  2. #include <set>
  3. #include <list>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <string>
  10. #include <bitset>
  11. #include <cstdio>
  12. #include <limits>
  13. #include <vector>
  14. #include <climits>
  15. #include <cstring>
  16. #include <cstdlib>
  17. #include <fstream>
  18. #include <numeric>
  19. #include <sstream>
  20. #include <iostream>
  21. #include <algorithm>
  22. #include <unordered_map>
  23.  
  24. using namespace std;
  25. int dep[30],dia[30], vis;
  26. vector<int> g[22];
  27. void dfs2(int x, int p){
  28.     vis++;
  29.     for(auto it : g[x]){
  30.         if(it != p)
  31.             dfs2(it,x);
  32.     }
  33. }
  34. bool istree(int n,int x,int y){
  35.     vis=0;
  36.     int nodes = __builtin_popcount(x);
  37.     int edges = y;
  38.     int start;
  39.     if(nodes-1 != edges)    return false;
  40.     for(int j=0;j<n;j++){
  41.         if((1<<j) & x){
  42.             start=j;
  43.             break;
  44.         }
  45.     }
  46.     dfs2(start,start);
  47.     if(vis == nodes)    return true;
  48.     else    return false;
  49. }
  50. void dfs(int x,int p){
  51.     dep[x] = dep[p] + 1;
  52.     for(auto it : g[x]){
  53.         if(it != p){
  54.             dfs(it, x);
  55.         }
  56.     }
  57. }
  58. int main() {
  59.     int n;
  60.     cin>>n;
  61.     int u[n],v[n];
  62.     for(int i=0;i<n-1;i++){
  63.  
  64.         cin>>u[i]>>v[i];
  65.         u[i]--;v[i]--;
  66.     }
  67.     for(int i=1;i<(1<<n);i++){
  68.         for(int j=0;j<=n;j++)
  69.             g[j].clear();
  70.         int cnt=0,st=-1;
  71.         for(int j=0;j<n-1;j++){
  72.             int x=u[j];
  73.             int y=v[j];
  74.             if((1<<x) & i){
  75.                 if((1<<y) & i){
  76.                     cnt++;
  77.                     g[x].push_back(y);
  78.                     g[y].push_back(x);
  79.                 }
  80.             }
  81.         }
  82.  
  83.         if(!istree(n,i,cnt))   continue;
  84.         int maxx = 0;
  85.         int node = 0;
  86.         memset(dep,0,sizeof(dep));
  87.         int start;
  88.         for(int j=0;j<n;j++){
  89.             if((1<<j) & i){
  90.                 start=j;
  91.                 break;
  92.             }
  93.         }
  94.         dfs(start,start);
  95.         for(int j=0;j<n;j++){
  96.             if(dep[j] > maxx){
  97.                 maxx = dep[j];
  98.                 node = j;
  99.  
  100.             }
  101.         }
  102.         memset(dep,0,sizeof(dep));
  103.         dfs(node,node);
  104.         maxx = 0;
  105.         for(int j=0;j<n;j++){
  106.             if(dep[j] > maxx){
  107.                 maxx = dep[j];
  108.                 node = j;
  109.  
  110.             }
  111.         }
  112.         dia[maxx-1]++;
  113.     }
  114.     for(int i=1;i<=n-1;i++)
  115.         cout<<dia[i]<<"\n";
  116.     return 0;
  117. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7rADZX
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!