# Super Maximum Cost Queries

# Super Maximum Cost Queries

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

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. :)

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.

999lovelyrani + 0 comments Hello guys, looking to enjoy a Delhi escort with fantastic body shape? I am Lovely Rani, a passionate Delhi babe, ready to fulfill all your dreams and aspirations. My breasts are fabulous and buttocks are naturally round. My arms and legs are in proper alignment with the rest of the body, making my overall personality, an impressive one. If you hire me, many benefits are associated to it. I will not only be happy to fulfill your demands, irrespective of how bizarre they are, I am a good companion too. For me, sex does not mean going between the legs or leaning on someone. I provide satisfaction in totality and completeness. Don't worry, if you are too busy to mingle, I am here to satisfy all your sexual fantasies, no matter how weird are they. With me in your bed, you enjoy a lot of varieties. I am ready to kiss and fondle every part of you that arouse and put you on. Hiring a Delhi call girl like me, provides you with an opportunity or a life-time experience. With me, you will definitely get much better results than you want. I consider my clients as valued customers and becomes friend of theirs. I always look forward to seeing, my clients again and come around. With me, you will take out the best escort experience of your life. I offer a variety of companionship, from someone to talk with to, to sexual pleasures. Many of my clients are regular and we know each other very well.

Our Partner links

http://www.lovelyrani.com/ https://www.lovepreet-kaur.com/ http://www.diljotkaur.com/ http://www.poonamdas.com/

www.Harmitkaur.com http://www.lovelyrani.com/ http://www.komalshetty.com/ https://www.shwetamahajan.com/ http://www.shreyasehgal.in/ http://www.delhiescorts.club/ https://www.manvikakkar.com/ http://www.anandjot.com/ http://www.diljotkaur.com/ http://www.ashnaimittal.com/ http://www.shreyasehgal.com/ http://www.kiranbajaj.com/

http://www.diljeetkaur.com/ http://www.lovelyrani.in/

http://www.poonamdas.com/

http://www.preetkaur.com/ http://www.shiplichawla.com http://www.shilpichawla.com/ http://www.komal-gupta.com/ http://www.delhicallgirls.club/ http://www.yalghis.in http://www.rasiga.in/ http://www.monika-tiwari.com/ http://www.mahima-singh.com/ http://jazlyn.in/

http://www.lovelykaur.com/ http://www.dilkaur.com/ https://www.poonamdas.com/ http://www.kavitabatra.com/ http://www.harshitakaur.com/ http://www.harmitkaur.com/ http://delhinightmassage.com/ http://www.delhimassageservice.com/ http://www.delhifemalemassage.com/ http://www.massagecenterindelhi.com/ http://www.mumbaimassagecenter.com/ http://www.mumbaifemalemassage.com/ http://www.massagecentermumbai.com/ http://massagecenterinmumbai.com/ http://www.massagecenterchandigarh.com/ http://www.massagecenterinhyderabad.com/ http://www.massagecenterbangalore.com/

quangminh_lee + 0 comments Thanks your! I want to you going to visit my website ( tÆ°á»£ng sivali ) statue sivali buddha composite.

willwon155 + 0 comments Thanks, for giving peace of a great blog it's really helpful for us and please post more blog like this for my future updates, once again thank you. If you want to grow your online status and promote your brand with some awesome digital strategies you check out our SEO Services Brampton.

darrinbratt123 + 0 comments Awesome thread! Check out this website for your web development needs.

charleswales914 + 0 comments you can refer to this link on maximizing cost queries

ak0368641 + 0 comments certain info for a very long time. Thank you and good luck [Payment Gateway UAE](https://uaewebsitedevelopment.com/payment-gateway-integration-services/ )

Sort 33 Discussions, By:

Please Login in order to post a comment