# Super Maximum Cost Queries

# Super Maximum Cost Queries

nikhil_gupta3591 + 0 comments For first time, i got hint from categroy, problem was posted for.

tpcemail + 0 comments fist i sort the edges,then i caculate the number of paths whos weight not bigger than a value,and put them into a table. last i look up in the table to get answer.it took me so long bu finally i pass all the case!

#include<iostream> #include<vector> using namespace std; //edge struct Edge { int dot1, dot2, weight; }; //for qsort int compare(const void *a, const void *b) { Edge* e1 = (Edge*)a; Edge* e2 = (Edge*)b; return e1->weight - e2->weight; } //number of paths whos weight is no bigger than weight. struct WeightPaths { long long weight, paths; }; //disjoint set's find int find_root(vector<int> &v, int x) { if (v[x] == x) return x; else { v[x] = find_root(v, v[x]); return v[x]; } } //binary search long long search(vector<WeightPaths> &weightPaths, int n) { int min = 0, max = weightPaths.size() - 1; long long result = 0; while (true) { if (max - min <= 1) break; int mean = (min + max) / 2; if (weightPaths[mean].weight > n) max = mean; else min = mean; } if (weightPaths[max].weight <= n) result = weightPaths[max].paths; else result = weightPaths[min].paths; return result; } int main() { int n, q; cin >> n >> q; Edge * Edges = new Edge[n - 1]; for (int i = 0;i < n - 1;i++) cin >> Edges[i].dot1 >> Edges[i].dot2 >> Edges[i].weight; qsort(Edges, n - 1, sizeof(Edge), compare); //sort vector<WeightPaths> weightPaths; WeightPaths wp; wp.weight = 0; wp.paths = 0; weightPaths.push_back(wp); vector<int> root(n + 1), count(n + 1); //disjoint set for (int i = 1;i < n + 1;i++) { root[i] = i; count[i] = 1; } int k = 0; while (k<n-1) { wp.weight = Edges[k].weight; while (k<n - 1 && Edges[k].weight == wp.weight) { int dot1 = Edges[k].dot1; int dot2 = Edges[k].dot2; int r1, r2; r1 = find_root(root, dot1); r2 = find_root(root, dot2); if (r1 != r2) { wp.paths += (long long)count[r2] * count[r1]; // caculate new paths root[r2] = r1; count[r1] += count[r2]; count[r2] = 0; } k++; } weightPaths.push_back(wp); } while (q--) { int l, r; cin >> l >> r; long long ln, rn, p; ln = search(weightPaths, l - 1); rn = search(weightPaths, r); p = rn - ln; cout << p << endl; } return 0; }

lingbo19_tang + 2 comments I'm confused, for example, query [1,2] of the graph should be {3,4} and {1,4}, not {1,3} because 1 -> 3 has a cost 3, am I missing something?

jabbarthejack + 0 comments aao kabi haveli pey samjatha

LittleFox + 0 comments Path cost is MAX of edges cost on the path and not SUM of edges cost.

annysmith020 + 0 comments Problem can easily solved by good idea, so you just have to get that idea and then you will never face any problem. So if you are finding solution related to your website issues then https://intrepidsoftware.com/fix-canonical-issues-in-a-website/ this is the right place.

anshumanc007 + 0 comments with proper use of disjoint sets,maps and sets(binary search,if u don't want to use sets) ,u can solve this problem. quite similar approach which is used for solving KOICOST of spoj.

Kartik1607 + 0 comments The editorials are bad at its best. It explains the solution and not the path to discovery. Here is my take on the solution.

So, we are given a weighted graph, and we are asked to print the number of paths in the graph having cost C.

*Cost of path*= C which is maximum weight of any edge in the path.Suppose I have a graph with N nodes, then

`Total number of edges = (N*(N-1))/2`

Value of C

**can be too big**so I cannot memoize for*all*values of C. But there are**atmost**`10^5`

different value of C, which**can be memoized**Idea : If I can get a graph whose each edge weight

*X or less than X*, then I can calculate number of edges in graph which is answer of cost X.Ah, hah. I can build a graph step by step considering cost of edges in increasing order. ie . First graph would have all edges with cost <= 1, then the graph would be updated for cost <= 2 and so on.

So,

**Step 1: Sort the input by cost**struct Q { int x; int y; long long cost; }; bool compareByCost(const Q &a, const Q &b) { return a.cost < b.cost; } sort(queries.begin(), queries.end(), compareByCost);

Now, I need to process the input, which is nothing but connecting node x with node y.

**Step 2: Creating the graph**for(auto q: queries) { int c = q.cost; join(q.x, q.y, c); }

Here, the join function

*finds the root of x, and root of y*and makes a union of the different tree.I can

**also update the answer**for cost c as well.// Returns root of node X and performs path compression. int getroot(int x) { if (root[x] == x) return x; root[x] = getroot(root[x]); return root[x]; } void join(int a, int b, long long c) { // Getting root of both a and b tress. int roota = getroot(a); int rootb = getroot(b); if(roota == rootb) return; // No need to do anything. They both belong to same tree already root[rootb] = roota; // Different trees, join them long long totalToRemove = 0; long long n = rcount[roota] ; // Number of nodes in tree A totalToRemove += (n*(n-1))/2; n = rcount[rootb] ; totalToRemove += (n*(n-1))/2; // Number of nodes in tree B rcount[roota] += rcount[rootb]; // Tree A now also contains all nodes of tree B. Update the count n = rcount[roota] ; long long totalToAdd = (n*(n-1))/2; // Number of nodes in updated Tree. costCounts[c] += (totalToAdd - totalToRemove); }

So, now my map contains answer for all the given cost. There are

*Q*queries, and at most*N*costs.*Q x N*will cause a Timeout. I now need to find a way to calculate sum for [L,R] fast.Currently my cost map returns returns cost of X, what if my cost map returned cost for all x <= X. A prefix sum!

**Step 3: Optimize cost counts prefix sum**long long maxC = 0; for(auto it: costCounts) { sum += it.second; costSum[it.first] = sum; maxC = max(maxC, it.first); }

Now, i can easily find out answer by binary searching :)

**Step 4: Spit answers**while(q--) { long long l,r; cin>>l>>r; r = min(r, maxC); long long lA = 0, rA; auto left = costSum.lower_bound(l); if (left != costSum.begin()){ --left; lA = left->second; } auto right = costSum.lower_bound(r); if (right->first > r) --right; rA = right->second; long long ans = rA - lA; cout<<ans<<"\n"; }

Any you get a good green Accepted Solution. :)

GeoMatt22 + 0 comments Interesting problem, took longer than I first thought!

One minor note on the editorial solution: It correctly notes that for a forest, the total number of paths is a sum over trees, paths. However the

*increase*in paths due to merging trees and can be computed more simply as .

safayat_rahaman + 1 comment testcase: 5 5 1 2 3 1 4 2 2 5 6 3 4 1 1 1 1 2 2 3 2 5 1 6

why output for 2-3 and 2-5 is 5 not 3? Am I missing something?

tanalam + 0 comments C= Max(all weight in a given path); So you have to find number of paths for which "Cs" lie in the given range [L,R]

muneebaadil + 1 comment For each of the Q queries, print the number of paths in T having cost C in the inclusive range [L, R] on a new line.

^ That is an ambigious sentence. Can you please elaborate?

tanalam + 0 comments C= Max(all weight in a given path); So you have to find number of paths for which Cs lie in the given range [L,R]

Sort 13 Discussions, By:

Please Login in order to post a comment