fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define dbg(x) cout << #x << " : " << x << endl
  5. #define rep(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define maxn 100005
  7. vector<ll> edges[maxn];
  8. ll n;
  9. ll dem = 0;
  10. ll dau[maxn];
  11. ll check[maxn], point_edges[maxn];
  12. map<pair<ll, ll>, ll> mapping;
  13. ll maax = 0;
  14. ll bd;
  15. struct cap
  16. {
  17.     ll x, y;
  18. };
  19. void bfs(ll source)
  20. {
  21.     dau[source] = 1;
  22.     queue<ll> q;
  23.     q.push(source);
  24.     while (!q.empty())
  25.     {
  26.         ll p = q.front();
  27.         q.pop();
  28.         bd = point_edges[p] + 1;
  29.         for (auto v : edges[p])
  30.         {
  31.             if (dau[v] == 1)
  32.                 continue;
  33.             dau[v] = 1;
  34.             mapping[{p, v}] = mapping[{v, p}] = point_edges[v] = bd % maax;
  35.             // cout<<"("<<p+1<<","<<v+1<<"):"<<bd%maax<<'\n';
  36.             bd++;
  37.             q.push(v);
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     // freopen("input.txt", "r", stdin);
  44.     // freopen("output.txt", "w", stdout);
  45.     memset(point_edges, -1, sizeof(point_edges));
  46.     cin >> n;
  47.     cap a[n];
  48.     for (ll i = 0; i < n - 1; i++)
  49.     {
  50.         ll u, v;
  51.         cin >> u >> v;
  52.         u--, v--;
  53.         edges[u].push_back(v);
  54.         edges[v].push_back(u);
  55.         a[i].x = u;
  56.         a[i].y = v;
  57.         mapping[{u, v}] = -1;
  58.         mapping[{v, u}] = -1;
  59.     }
  60.  
  61.     ll vt;
  62.     for (ll i = 0; i < n; i++)
  63.     {
  64.         // cout<<i+1<<"-->";
  65.         // for(auto v: edges[i]) cout<<v<<" ";
  66.         // cout<<'\n';
  67.         ll tmp = edges[i].size();
  68.         if (tmp > maax)
  69.         {
  70.             maax = tmp;
  71.             vt = i;
  72.         }
  73.     }
  74.     cout << maax << '\n';
  75.     bfs(0);
  76.     // cout<<"--------\n";
  77.     for (ll i = 0; i < n - 1; i++)
  78.         cout << mapping[{a[i].x, a[i].y}] + 1 << '\n';
  79.     return 0;
  80. }
Success #stdin #stdout 0.01s 7660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/n9BPDO
language:
C++14 (gcc 8.3)
created:
3 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!