Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <fstream>
- #include <ctime>
- #include <vector>
- #include <string>
- using namespace std;
- int n = 0;
- int MIN = 2 * 100001;
- vector<bool> used;
- long long time_cur = 0;
- struct node {
- vector<node*> parents;
- vector<node*> childs;
- int timein = 0;
- int timeout = 0;
- int num = 0;
- int weight = -1;
- };
- void dfs(node* cur, int mpot) {
- used[cur->num] = true;
- time_cur++;
- cur->timein = time_cur;
- for (int i = 1; i <= mpot; i++) {
- if (cur->parents[i - 1] != nullptr) {
- cur->parents[i] = (cur->parents[i - 1]->parents[i - 1]);
- }
- }
- for (auto child : cur->childs) {
- if (child != cur) {
- dfs(child, mpot);
- }
- }
- time_cur++;
- cur->timeout = time_cur;
- }
- node* lca(node* first, node* second) {
- if (first->timein <= second->timein && first->timeout >= second->timeout) {
- return first;
- }
- else if (second->timein <= first->timein && second->timeout >= first->timeout) {
- return second;
- }
- for (int i = first->parents.size() - 1; i >= 0; i--) {
- if (first->parents[i] == nullptr) {
- first->parents[i] = first;
- }
- if (second->parents[i] == nullptr) {
- second->parents[i] = second;
- }
- if (first->parents[i]->timein >= second->timein || first->parents[i]->timeout <= second->timeout) {
- first = first->parents[i];
- }
- }
- first = first->parents[0];
- return first;
- }
- int min_pot(int x) {
- int a = 0;
- while ((1 << a) <= x) {
- a++;
- }
- return a;
- }
- int main() {
- scanf("%d", &n);
- vector<node*> nodes(n);
- for (int i = 0; i < n; i++) {
- nodes[i] = new node;
- nodes[i]->num = i;
- }
- for (int i = 1; i < n; i++) {
- int p = 0, y = 0;
- scanf("%d %d", &p, &y);
- nodes[i]->parents.push_back(nodes[p - 1]);
- nodes[p - 1]->childs.push_back(nodes[i]);
- nodes[i]->weight = y;
- }
- int mpot = min_pot(n);
- mpot++;
- for (int i = 0; i < n; ++i) {
- nodes[i]->parents.resize(mpot);
- }
- used.resize(n, false);
- for (int i = 0; i < n; i++) {
- if (!used[i])
- dfs(nodes[i], mpot - 1);
- }
- int MIN = 2 * 100001;
- int m = 0;
- scanf("%d", &m);
- for (int i = 0; i < m; i++) {
- int a, b;
- scanf("%d %d", &a, &b);
- node *a1 = nodes[a - 1];
- node *b1 = nodes[b - 1];
- node *ver = lca(a1, b1);
- for (int i = a1->parents.size() - 1; i >= 0; i--) {
- if (a1->weight < MIN && a1->weight != -1) {
- MIN = a1->weight;
- }
- if (a1->parents[i] != nullptr) {
- a1->parents[i] = a1;
- }
- if (a1->weight < MIN && a1->weight != -1) {
- MIN = a1->weight;
- }
- }
- for (int i = b1->parents.size() - 1; i >= 0; i--) {
- if (b1->weight < MIN && b1->weight != -1) {
- MIN = b1->weight;
- }
- if (b1->parents[i] != nullptr) {
- b1->parents[i] = b1;
- }
- if (b1->weight < MIN && b1->weight != -1) {
- MIN = b1->weight;
- }
- }
- }
- printf("%d\n", MIN);
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement