Advertisement
Guest User

Untitled

a guest
May 24th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.32 KB | None | 0 0
  1. // 53cpp.cpp: определяет точку входа для консольного приложения.
  2. //
  3. #pragma comment(linker, "/STACK:67108864")
  4. //#include "stdafx.h"
  5. #include <iostream>
  6. #include <fstream>
  7. #include <vector>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. int max_edge;
  13. int n;
  14. int logn;
  15. void initialize(int, int, int, int);
  16. vector<int> path[200001];
  17. vector<int> curr_max[200001];
  18. vector<int> adj_list[200001];
  19. vector<int> fines[200001];
  20. int levels[200001];
  21.  
  22. int main() {
  23.     ifstream fin("input.txt");
  24.     ofstream fout("output.txt");
  25.     fin >> n;
  26.     logn = 1;
  27.     int pow = 1;
  28.     while (pow <= n) {
  29.         pow *= 2;
  30.         logn++;
  31.     }
  32.     //cout << logn;
  33.     int s;
  34.     int f;
  35.     int w;
  36.    
  37.     for (int i = 0; i < n; i++) {
  38.         for (int j = 0; j < logn + 1; j++) {
  39.             path[i].push_back(0);
  40.             curr_max[i].push_back(-INT32_MAX);
  41.         }
  42.     }
  43.    
  44.     for (int i = 0; i < n - 1; i++) {
  45.         fin >> s;
  46.         fin >> f;
  47.         s--;
  48.         f--;
  49.         fin >> w;
  50.         adj_list[s].push_back(f);
  51.         fines[s].push_back(w);
  52.         adj_list[f].push_back(s);
  53.         fines[f].push_back(w);
  54.     }
  55.     initialize(0, 0, 0, -INT32_MAX);
  56.     //cout << "ho";
  57.     int m;
  58.     fin >> m;
  59.     for (int i = 0; i < m; i++) {
  60.         fin >> s;
  61.         fin >> f;
  62.         if (s == f)
  63.             fout << 0 << endl;
  64.         else {
  65.             s--;
  66.             f--;
  67.             max_edge = INT32_MIN;
  68.             if (levels[f] > levels[s]) {
  69.                 int pow = 1 << logn;
  70.                 int ind = logn;
  71.                 int diff = levels[f] - levels[s];
  72.                 for (; ind >= 0;) {
  73.                     if (pow <= diff) {
  74.                         max_edge = max(max_edge, curr_max[f][ind]);
  75.                         f = path[f][ind];
  76.                         diff = levels[f] - levels[s];
  77.                     }
  78.                     pow = pow >> 1;
  79.                     ind--;
  80.                 }
  81.                 if (f != s) {
  82.                     int j = logn;
  83.                     while (j >= 0) {
  84.                         if (path[s][j] != path[f][j]) {
  85.                             max_edge = max(curr_max[s][j], max_edge);
  86.                             max_edge = max(max_edge, curr_max[f][j]);
  87.                             s = path[s][j];
  88.                             f = path[f][j];
  89.                         }
  90.                         j--;
  91.                     }
  92.                     if (f != s) {
  93.                         max_edge = max(curr_max[s][0], max_edge);
  94.                         max_edge = max(curr_max[f][0], max_edge);
  95.                     }
  96.                 }
  97.             }
  98.             else {
  99.                 int pow = 1 << logn;
  100.                 int ind = logn;
  101.                 int diff = levels[s] - levels[f];
  102.                 for (; ind >= 0;) {
  103.                     if (pow <= diff) {
  104.                         max_edge = max(max_edge, curr_max[s][ind]);
  105.                         s = path[s][ind];
  106.                         diff = levels[s] - levels[f];
  107.                     }
  108.                     pow = pow >> 1;
  109.                     ind--;
  110.                 }
  111.                 if (f != s) {
  112.                     int j = logn;
  113.                     while (j >= 0) {
  114.                         if (path[s][j] != path[f][j]) {
  115.                             max_edge = max(curr_max[s][j], max_edge);
  116.                             max_edge = max(max_edge, curr_max[f][j]);
  117.                             s = path[s][j];
  118.                             f = path[f][j];
  119.                         }
  120.                         j--;
  121.                     }
  122.                     if (f != s) {
  123.                         max_edge = max(curr_max[s][0], max_edge);
  124.                         max_edge = max(curr_max[f][0], max_edge);
  125.                     }
  126.                 }
  127.             }
  128.             fout << max_edge << endl;
  129.         }
  130.     }
  131.    
  132.     return 0;
  133. }
  134.  
  135. void initialize(int curr, int prev, int lev, int fine) {
  136.     path[curr][0] = prev;
  137.     curr_max[curr][0] = fine;
  138.     levels[curr] = lev;
  139.     for (int i = 1; i <= logn; i++) {
  140.         int prev_step = path[curr][i - 1];
  141.         path[curr][i] = path[prev_step][i - 1];
  142.     }
  143.     for (int i = 1; i <= logn; i++) {
  144.         int prev_step = path[curr][i - 1];
  145.         curr_max[curr][i] = max(curr_max[curr][i - 1], curr_max[prev_step][i - 1]);
  146.     }
  147.     for (int i = 0; i < adj_list[curr].size(); i++) {
  148.         if (adj_list[curr][i] != prev) {
  149.             initialize(adj_list[curr][i], curr, lev + 1, fines[curr][i]);
  150.         }
  151.     }
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement