fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 1e5 + 5;
  38. struct Node {
  39.     int distLeft, distRight, minHigh, maxHigh;
  40.     Node(int _distLeft = -inf, int _distRight = -inf, int _minHigh = inf, int _maxHigh = -inf):
  41.         distLeft(_distLeft), distRight(_distRight), minHigh(_minHigh), maxHigh(_maxHigh) {}
  42.  
  43.     friend Node combine(const Node &L, const Node &R) {
  44.         Node res;
  45.         res.distLeft = max({L.distLeft, R.distLeft, L.maxHigh - 2 * R.minHigh});
  46.         res.distRight = max({L.distRight, R.distRight, R.maxHigh - 2 * L.minHigh});
  47.         res.maxHigh = max(L.maxHigh, R.maxHigh);
  48.         res.minHigh = min(L.minHigh, R.minHigh);
  49.         return res;
  50.     }
  51. } node[N << 2];
  52. int numNode, numQuery;
  53. vector<int> G[N];
  54. int tour[N], timeIn[N], timeOut[N], high[N], par[N][18], lenTour;
  55.  
  56. void dfs(int u) {
  57.     timeIn[u] = ++lenTour;
  58.     tour[lenTour] = u;
  59.     for(int v : G[u]) if (v != par[u][0]) {
  60.         high[v] = high[u] + 1;
  61.         par[v][0] = u;
  62.         dfs(v);
  63.         tour[++lenTour] = u;
  64.     }
  65.     timeOut[u] = lenTour;
  66. }
  67.  
  68. int jump(int u, int k) {
  69.     if (k <= 0) return u;
  70.     REP(j, 18) if (BIT(k, j))
  71.         u = par[u][j];
  72.     return u;
  73. }
  74.  
  75. int LCA(int u, int v) {
  76.     if (high[u] < high[v]) swap(u, v);
  77.     u = jump(u, high[u] - high[v]);
  78.     if (u == v) return u;
  79.     RED(j, 18) if (par[u][j] != par[v][j]) {
  80.         u = par[u][j];
  81.         v = par[v][j];
  82.     }
  83.     return par[u][0];
  84. }
  85.  
  86. int dist(int u, int v) {
  87.     int p = LCA(u, v);
  88.     return high[u] + high[v] - 2 * high[p];
  89. }
  90.  
  91. void build(int id, int l, int r) {
  92.     if (l == r) {
  93.         node[id].maxHigh = node[id].minHigh = high[tour[l]];
  94.         node[id].distLeft = node[id].distRight = -high[tour[l]];
  95.         return;
  96.     }
  97.     int mid = (l + r) >> 1;
  98.     build(id << 1, l, mid);
  99.     build(id << 1 | 1, mid + 1, r);
  100.     node[id] = combine(node[id << 1], node[id << 1 | 1]);
  101. }
  102.  
  103. Node getDist(int id, int l, int r, int u, int v) {
  104.     if (l > v || r < u || u > v) return Node();
  105.     if (u <= l && r <= v) return node[id];
  106.     int mid = (l + r) >> 1;
  107.     Node L = getDist(id << 1, l, mid, u, v);
  108.     Node R = getDist(id << 1 | 1, mid + 1, r, u, v);
  109.     return combine(L, R);
  110. }
  111.  
  112. int maxDist(int node, int l, int r) {
  113.     if (l > r) return 0;
  114.     Node L = getDist(1, 1, lenTour, l, min(timeIn[node], r));
  115.     Node R = getDist(1, 1, lenTour, max(l, timeIn[node]), r);
  116.     return max(L.distLeft, R.distRight) + high[node];
  117. }
  118.  
  119. void init(void) {
  120.     cin >> numNode;
  121.     FOR(i, 1, numNode) G[i].clear();
  122.     FOR(i, 2, numNode) {
  123.         int u, v;
  124.         cin >> u >> v;
  125.         G[u].pb(v);
  126.         G[v].pb(u);
  127.     }
  128. }
  129.  
  130. void process(void) {
  131.     lenTour = 0;
  132.     dfs(1);
  133.     FOR(j, 1, 17) FOR(i, 1, numNode)
  134.         par[i][j] = par[par[i][j - 1]][j - 1];
  135.  
  136.     FOR(i, 1, 4 * numNode) node[i] = Node();
  137.     build(1, 1, lenTour);
  138.  
  139.     cin >> numQuery;
  140.     while(numQuery--) {
  141.         int u, v;
  142.         cin >> u >> v;
  143.         if (high[u] < high[v]) swap(u, v);
  144.  
  145.         int w = jump(u, dist(u, v) / 2), ans = 0;
  146.         if (w == LCA(u, v)) w = jump(u, high[u] - high[w] - 1);
  147.  
  148.         maximize(ans, maxDist(u, timeIn[w], timeOut[w]));
  149.  
  150.         if (timeIn[v] < timeIn[w]) {
  151.             maximize(ans, maxDist(v, 1, timeIn[v]));
  152.             Node L = getDist(1, 1, lenTour, timeIn[v], timeIn[w] - 1);
  153.             Node R = getDist(1, 1, lenTour, timeOut[w] + 1, lenTour);
  154.             Node res = combine(L, R);
  155.             maximize(ans, res.distRight + high[v]);
  156.         } else if (timeIn[w] <= timeIn[v] && timeOut[v] <= timeOut[w]) {
  157.             maximize(ans, maxDist(v, 1, timeIn[w] - 1));
  158.             maximize(ans, maxDist(v, timeOut[w] + 1, lenTour));
  159.         } else {
  160.             maximize(ans, maxDist(v, timeIn[v], lenTour));
  161.             Node L = getDist(1, 1, lenTour, 1, timeIn[w] - 1);
  162.             Node R = getDist(1, 1, lenTour, timeOut[w] + 1, timeIn[v]);
  163.             Node res = combine(L, R);
  164.             maximize(ans, res.distLeft + high[v]);
  165.         }
  166.  
  167.         cout << ans << '\n';
  168.     }
  169. }
  170.  
  171. int main() {
  172.     ios_base::sync_with_stdio(0);
  173.     cin.tie(0); cout.tie(0);
  174.     if (fopen(task".inp", "r")) {
  175.         freopen(task".inp", "r", stdin);
  176.         freopen(task".out", "w", stdout);
  177.     }
  178.     int tc = 1;
  179.     cin >> tc;
  180.     while(tc--) {
  181.         init();
  182.         process();
  183.     }
  184.     return 0;
  185. }
  186.  
Success #stdin #stdout 0.01s 13948KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z3mJoL
language:
C++14 (gcc 8.3)
created:
2 days 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!