Cerinta completa

Victoria has a tree, , consisting of nodes numbered from to . Each edge from node to in tree has an integer weight, .

Let’s define the cost, , of a path from some node to some other node as the maximum weight () for any edge in the unique path from node to node .

Victoria wants your help processing queries on tree , where each query contains integers, and , such that . For each query, she wants to print the number of different paths in that have a cost, , in the inclusive range .

It should be noted that path from some node to some other node is considered same as path from node to i.e is same as .

Input Format

The first line contains space-separated integers, (the number of nodes) and (the number of queries), respectively.
Each of the subsequent lines contain space-separated integers, , , and , respectively, describing a bidirectional road between nodes and which has weight .
The subsequent lines each contain space-separated integers denoting and .

Constraints

Scoring

  • for of the test data.
  • for of the test data.

Output Format

For each of the queries, print the number of paths in having cost in the inclusive range on a new line.

Sample Input

5 5
1 2 3
1 4 2
2 5 6
3 4 1
1 1
1 2
2 3
2 5
1 6

Sample Output

1
3
5
5
10

Explanation

:
:
:
:
…etc.

Limbajul de programare folosit: cpp14

Cod:

#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <set>
#include <map>
#include <complex>
#include <iostream>
#include <time.h>
#include <stack>
#include <stdlib.h>
#include <memory.h>
#include <bitset>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

const int MaxN = 1e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, q, sz[MaxN], who[MaxN];
vector < pair < int, int > > graph[MaxN];
long long cnt = 0;

int get(int v) {
  return v == who[v] ? v : who[v] = get(who[v]);
}

void unite(int a, int b) {
  a = get(a);
  b = get(b);
  if (a == b) {
    return;
  }
  if (a & 1) {
    swap(a, b);
  }
  cnt += 1LL * sz[a] * sz[b];
  sz[b] += sz[a];
  who[a] = b;
}

int main() {
//  freopen("input.txt", "r", stdin);
//  ios::sync_with_stdio(false);
//  cin.tie(NULL);
  scanf("%d%d", &n, &q);
  vector < pair < int, pair < int, int > > > edges;
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    graph[u].push_back(make_pair(v, w));
    graph[v].push_back(make_pair(u, w));
    edges.push_back(make_pair(w, make_pair(u, v)));
  }
  vector < pair < int, long long > > ans;
  ans.push_back(make_pair(0, 0LL));
  for (int i = 1; i <= n; ++i) {
    who[i] = i;
    sz[i] = 1;
  }
  sort(edges.begin(), edges.end());
  for (int i = 0, j; i < (int)edges.size(); i = j) {
    for (j = i; j < (int)edges.size() && edges[j].first == edges[i].first; ++j);
    for (int k = i; k < j; ++k) {
      unite(edges[k].second.first, edges[k].second.second);
    }
    ans.push_back(make_pair(edges[i].first, cnt));
  }
  ans.push_back(make_pair(MOD, ans.back().second));
  for (int i = 0; i < q; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%lld\n", (--upper_bound(ans.begin(), ans.end(), make_pair(r, 1LL << 60)))->second -
           (--lower_bound(ans.begin(), ans.end(), make_pair(l, -1LL << 60)))->second);
  }
  return 0;
}

Scor obtinut: 1.0

Submission ID: 464653230

Link challenge: https://www.hackerrank.com/challenges/maximum-cost-queries/problem

Super Maximum Cost Queries