Alice is playing with a tree consisting of N nodes, each with its own unique value. For any two distinct nodes x and y, she wants to compute a special score h(x, y) for each pair. Here’s how she defines it:
Maximum Value on Path f(x, y): This is the highest value among all nodes on the path connecting x and y.
Minimum Value on Path g(x, y): This is the lowest value among all nodes on the same path.
Special Score h(x, y): This is simply the product of f(x, y) and g(x, y), or h(x,y)=f(x,y)*g(x,y)
Alice wants to calculate the total sum of h(x, y) for every unique pair of nodes (x, y) where x ≠ y. Since the result might be huge, give the final answer modulo 1e9 + 7
Input Format The first line contains an integer N denoting the number of nodes in the tree.
The second line contains N space-separated integers A1, A2, ..., AN denoting the values associated with each node.
The next N — 1 lines each contain two integers ui, vi, denoting an edge between nodes ui and vi.
constraints-> 1≤N≤2×10^5
ANY IDEA FOR THIS PROBLEM?
anyone pls initiate can't think of anything!!
Dominater069 jiangly tourist pashka aryanc403 please tell any thought
I think this problem can be solved with centroid decomposition.
lets fix centroid, now for all in this component get mn[u] and mx[u].
Now we are interested to find min(mn[u], mn[v]) * max(mx[u], mx[v]) for all u, v such that u and v is not in same subtree in centroid decomposition.
One way to do that is when you additing new node to count with other nodes from different subtrees, posible cases is maximum is now greater than prevision maximum or minimim is smaller than previuos minimum (can`t happend both of this cases because contradiction and all values is different) and now is only to calculate for this two cases(case work).
correct me if i am wrong.
i have thought this but for u ,v which is not in same subtree you have to do for loop for all previous added nodes and current subtree nodes which will be O(n^2) so wont work.I am also stuck in this loop only how to optimize it
mx[u] = mx[parent] and mn[u] = mn[parent] -> that mean nothing will change and you can use ans[parent] + min(a[u], a[parent]) * max(a[v], a[parent])
you have two more case
mn[u] < mn[parent] and mx[u] = mx[parent]
mx[u] > mx[parent] and mn[u] = mn[parent]
i think this two cases also can be done with ans from parent but i dont have time now to tink you need alone to think about this (am not sure is this solution)
i am hope i helped.
Shayan neal Benq rainboy shiven Chahel Prady itzzRaghav JagguBandar Please someone help us in this Problem.
It will be really helpful if someone tell the solution.
It Doesn't work
Can use Centroids in this tasks. How? Let's say we choose vertex v which is centroid for our tree Main idea of centroid decomposicion — get the ans for path, that contains centroid. Delete our centroid from the graph. Use our solution for every component
How to get the ans? We have sums of f(a) * g(a). lets get a two versions of segment tree in which we will contains sum of g(a) for f(a) if we started in our centroid. Difference is that when leaf in tree1 will contain x, in tree2 we will save id * x, where id — in our meaning is minimum on our path. We also have 2 versions dfs. We will start them from each child of centroid (with thinking, that centroid was visited). In first dfs we will calculate answer, in second we will update ST. In first dfs we save min, max on path from centroid. And get from the tree1 sum on (min, inf) = Sum1 and from tree2 get sum on (0, min — 1) = Sum2. if we end in this vertex is min * Sum1 + Sum2 (plus to global answer) In second dfs we will save min, max. for tree we do update(min, max) means to vertex with num "min" add max and in tree2 we do update (min, min * max) -> means to vertex min add min * max
can you elaborate bit what sgtree1 is storing and what segtree 2 is storing
I think it is wrong what you are trying to do is that find sum of max whose min is bigger than our current min which is SUM1 and add min*sum1 and find sum of mn*mx for those nodes who have min bigger than current node min and which is SUM2 and add min*sum1 + sum2 to global ans correct me if i am wrong?
now lets talk on sum1 for all those nodes whose min is bigger than curren node min then we can say that g(x,y) is fixed for this node that is current min but saying f(x,y) will be there max its wrong please correct if i am wrong and please elaborate your approach
you are always assuming that f(x,y) is coming from different subtree i think its wrong
Just use Persistent ST
umm cant think how to use it please tell or share the code if you can
Consider joining two paths that share a common node at the ends where the first path has (min1, max1) and the second has (min2, max2). If we imagine them as points on the 2d plane we can split the formula for the H-value of the joined path into 4 cases based on which quadrant the second is in relative to the first.
Ultimately maybe some divide-and-conquer/centroid idea with 2d dynamic segment trees could work. Really any data structure that stores (2d point, value) pairs and we can query for sum in a 2d region would allow us to handle all the updates. Then the merge step can just handle each of the four quadrant cases separately
i dont have idea about 2d dynamic segment tree it will be helpful if you can share your code
basically i understood
lets say currentnode have min1,max1 now we need some ds which can handle four cases
bring sum of all previous added nodes max whose min is >= min1 ans max>=max1 then we can add min1*sum
now bring sum of all min whose min is<min1 and max<max1 then we can add max1*sum
now bring cnt of all such prevoios nodes such that we can have min>min1 and max<max1 so we can add cnt*min1*max1
now bring sum of min*max such that minmax1
can 2d dynamic segment tree do this?
Errichto any idea for this problem?
an annoying Indian
a $$$O(N\log N)$$$-time solution exists.
it will be really helpful if you share your thoughts and code if you can..it will be really helpful
Could you please share your approach for the O(NlogN) solution you mentioned? I'd really appreciate your insight.