fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FOR(i,a,b)      for (int i = (a), _b = (b); i <= (_b); ++i)
  6. #define FORD(i,a,b)     for (int i = (a), _b = (b); i >= (_b); --i)
  7. #define REP(i, n)        for (int i = (0), _n = (n); i < _n; ++i)
  8. #define getBit(mask,i)  (((mask) >> (i)) & (1LL))
  9. #define MASK(x)            (1LL << (x))
  10. #define allof(x)        begin(x), end(x)
  11. #define el              cout << '\n';
  12.  
  13. //--Compare------------------------------------------------------------------------------------
  14. template<class X, class Y>
  15.     inline bool maximize(X &x, const Y &y){ return (x < y) ? x = y, 1 : 0; }
  16.  
  17. template<class X, class Y>
  18.     inline bool minimize(X &x, const Y &y){ return (x > y) ? x = y, 1 : 0; }
  19.  
  20. //--Process------------------------------------------------------------------------------------
  21.  
  22. //#define int             long long
  23.  
  24. typedef pair <int, int> pii;
  25. #define fi              first
  26. #define se              second
  27.  
  28. constexpr int MAXN = 160016;
  29. int n, q;
  30. vector <int> adj[MAXN];
  31.  
  32. namespace subtask2
  33. {
  34.     void solve(void)
  35.     {
  36.         int LG = __lg(n);
  37.         vector <int> h(n + 1, 0);
  38.         vector <vector<int>> par(n + 1, vector <int> (LG + 1, 0));
  39.  
  40.         function <void(int, int, bool)> dfs = [&](int u, int p, bool ok)
  41.         {
  42.             if (ok)
  43.             {
  44.                 par[u][0] = p;
  45.                 FOR(i, 1, LG) par[u][i] = par[par[u][i - 1]][i - 1];
  46.             }
  47.  
  48.             for (int v : adj[u])
  49.             {
  50.                 if (v == p) continue;
  51.                 h[v] = h[u] + 1;
  52.                 dfs(v, u, ok);
  53.             }
  54.         };
  55.  
  56.         function <int(int, int)> lca = [&](int u, int v)
  57.         {
  58.             if (h[u] < h[v]) swap(u, v);
  59.  
  60.             for (int d = h[u] - h[v], nxt; d; d ^= MASK(nxt))
  61.             {
  62.                 nxt = 31 - __builtin_clz(d);
  63.                 u = par[u][nxt];
  64.             }
  65.             if (u == v) return u;
  66.  
  67.             FORD(i, LG, 0) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  68.             return par[u][0];
  69.         };
  70.  
  71.         int root = 0, D = 0;
  72.         dfs(1, 0, 0);
  73.         FOR(u, 1, n)
  74.         {
  75.             if (maximize(D, h[u])) root = u;
  76.             h[u] = 0;
  77.         }
  78.         dfs(root, 0, 1);
  79.         FOR(u, 1, n) maximize(D, h[u]);
  80.  
  81.         vector <pair<int,int>> ord;
  82.  
  83.         FOR(u, 1, n) FOR(v, 1, n)
  84.         if (u == v) continue;
  85.         else if (h[u] + h[v] - 2 * h[lca(u, v)] == D) ord.emplace_back(u, v);
  86.  
  87.         cout << ord.size() << '\n';
  88.         sort(allof(ord));
  89.  
  90.         while (q--)
  91.         {
  92.             int pos; cin >> pos;
  93.             if (pos > ord.size()) cout << "0 0\n";
  94.             else cout << ord[pos - 1].fi << ' ' << ord[pos - 1].se << '\n';
  95.         }
  96.     }
  97. }
  98.  
  99. signed main(void)
  100. {
  101.     cin.tie(nullptr)->sync_with_stdio(false);
  102.     cin.exceptions(cin.failbit);
  103.  
  104.     #define task "BAI3"
  105.     if (fopen(task".INP", "r"))
  106.     {
  107.        freopen(task".INP", "r", stdin);
  108.        freopen(task".OUT", "w", stdout);
  109.     }
  110.     //--OpenFile-------------------------------------------------------------------------------
  111.  
  112.     int T; cin >> T;
  113.     while (T--)
  114.     {
  115.         cin >> n >> q;
  116.         FOR(u, 1, n) adj[u].clear();
  117.         FOR(i, 2, n)
  118.         {
  119.             int u, v; cin >> u >> v;
  120.             adj[u].emplace_back(v);
  121.             adj[v].emplace_back(u);
  122.         }
  123.  
  124.         subtask2::solve();
  125.     }
  126.  
  127.     cerr << (1.0 * clock() / CLOCKS_PER_SEC);
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout #stderr 0.01s 7388KB
comments (?)
stdin
copy 
1
4 3
1 2
1 3
1 4
1
4
7
stdout
copy 
6
2 3
3 4
0 0
stderr
copy 
0.006921
https://ideone.com/0sn9dx
language:
C++ (gcc 8.3)
created:
9 hours 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!