fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define SPED                                                                                                           \
  4.     ios_base::sync_with_stdio(false);                                                                                  \
  5.     cin.tie(0);                                                                                                        \
  6.     cout.tie(0);
  7.  
  8. #define endl "\n"
  9. #define fi first
  10. #define se second
  11. #define lint long long
  12.  
  13. const lint INF = 0x1f1f1f1f1f1f1f1f;
  14. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  15.  
  16. using namespace std;
  17.  
  18. int n, dist[55];
  19. vector<pair<int, lint>> adj[55];
  20. vector<pair<lint, int>> x[55];
  21. vector<int> vec;
  22.  
  23. void dfs(int now, int par, int br)
  24. {
  25.     x[br].emplace_back(dist[now], now);
  26.     for (auto [v, w] : adj[now])
  27.     {
  28.         if (v == par)
  29.             continue;
  30.         dist[v] = dist[now] + w;
  31.         dfs(v, now, br);
  32.     }
  33. }
  34.  
  35. void make_ans(int root)
  36. {
  37.     dist[root] = 0;
  38.     vector<lint> vals;
  39.     vector<int> childs;
  40.     for (auto [v, w] : adj[root])
  41.     {
  42.         x[v].clear();
  43.         childs.emplace_back(v);
  44.         dist[v] = dist[root] + w;
  45.         dfs(v, root, v);
  46.  
  47.         for (auto [w, z] : x[v])
  48.             vals.emplace_back(w);
  49.     }
  50.  
  51.     sort(vals.begin(), vals.end());
  52.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  53.  
  54.     for (auto val : vals)
  55.     {
  56.         vector<int> temp;
  57.         for (auto c : childs)
  58.         {
  59.             sort(x[c].begin(), x[c].end());
  60.             auto it = lower_bound(x[c].begin(), x[c].end(), make_pair(val, -1));
  61.  
  62.             if (it != x[c].end() and (*it).fi == val)
  63.                 temp.emplace_back((*it).se);
  64.  
  65.             // if (root == 9 and val == 3 and c == 10)
  66.             // {
  67.             //     auto it = lower_bound(x[c].begin(), x[c].end(), make_pair(val, -1));
  68.  
  69.             //     for (auto [bel, nig] : x[c])
  70.             //         cout << bel << " " << nig << endl;
  71.  
  72.             //     if (it == x[c].end())
  73.             //         cout << "KHONG TON TAI";
  74.             //     else
  75.             //         cout << (*it).fi << " " << (*it).se << endl;
  76.             // }
  77.         }
  78.  
  79.         if (temp.size() > vec.size())
  80.             vec = temp;
  81.  
  82.         // if (root == 9)
  83.         //     for (auto z : temp)
  84.         //         cout << "val : " << val << " " << z << endl;
  85.     }
  86. }
  87.  
  88. signed main()
  89. {
  90.     if (fopen("egalitarianism3.inp", "r"))
  91.     {
  92.         freopen("egalitarianism3.inp", "r", stdin);
  93.         freopen("egalitarianism3.out", "w", stdout);
  94.     }
  95.     SPED;
  96.     cin >> n;
  97.     for (int i = 1; i < n; i++)
  98.     {
  99.         int l, r;
  100.         lint w;
  101.         cin >> l >> r >> w;
  102.         adj[l].emplace_back(r, w);
  103.         adj[r].emplace_back(l, w);
  104.     }
  105.  
  106.     if (n <= 2)
  107.     {
  108.         cout << n << endl;
  109.         for (int i = 1; i <= n; i++)
  110.             cout << i << " ";
  111.         return 0;
  112.     }
  113.  
  114.     for (int root = 1; root <= n; root++)
  115.         make_ans(root);
  116.  
  117.     if (vec.size() <= 2)
  118.     {
  119.         cout << 2 << endl;
  120.         cout << 1 << " " << 2, 0;
  121.     }
  122.     else
  123.     {
  124.         cout << vec.size() << endl;
  125.         for (auto z : vec)
  126.             cout << z << " ";
  127.     }
  128. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gd6NRh
language:
C++14 (gcc 8.3)
created:
1 day 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!