Given a weighted tree consisting of N vertices and N-1 edges. In a single operation, you can select an edge and increase or decrease its weight by 1. You are given Q queries and a query consisting of two vertices U and V, determine the minimum number of operations to be performed such that the weight of each edge of the path from vertex U to vertex V becomes the same.
With constraint up to 10^5;
I don't have any approach simpler than it, which requires persistant segment tree.
We know that, when we have two (multi)sets $$$S, T$$$, which both maintained by segment tree(every position stand for one value), and we want $$$T - S$$$, we can just use the "subtraction" of two segment trees.
Then look at the problem, think how to get the (multi)set of a path $$$(u, v)$$$.
Now the problem has been simplified as: find minimal cost, as the original problem said, of a set $$$S$$$.
It's clear that we optimally choose the medium($$$m$$$) of $$$S$$$ as target, and each $$$x\in S$$$ contributes $$$|m-x|$$$. Finding medium and calculating $$$\sum_{x\in [l, r]} x$$$ are things we need to do, and both of them can be done by a segment tree.
Complexity: $$$O((n+q) \log U)$$$.
I've never heard about persistant segment tree, can you explain how it works and what it can do?
sry for late reply...
"Persistent" means, when we modify on segment tree $$$T$$$ and get a new tree $$$T'$$$, $$$T$$$ is still accessible. For example, if you want to change a position, a path of length $$$O(\log n)$$$ can be found, we will copy a new path instead of simply changing it. Then the original tree is not modified actually.
In this problem, we apply "insert a number $$$x$$$ into the set" operation, which is to find the path of position $$$x$$$ and get all the nodes on the path added $$$x$$$. Each node maintains $$$\sum_{x\in [l, r]} x$$$. But the previous version is still needed, so just get it persistent.
To understand 'subtraction', think about two nodes $$$x, y$$$ respectively on two trees $$$T_1, T_2$$$, representing a same number range $$$[l, r]$$$. $$$x-y$$$ exactly equals to the maintained value of node representing $$$[l, r]$$$ on tree $$$T_1-T_2$$$.
I asked about persistant segment trees, not about persistent.
First, figure out how to do this with an array. It can be proven that it's optimal to set all numbers to the median(any in the case of 2). Let $$$M$$$ = median. To find $$$M$$$, you need a DS that can get the xth number. You'd also need the following to get the answer: The sum of all numbers <= $$$M$$$ and count of all numbers <= $$$M$$$. (We can get the same values of greater than $$$M$$$ by subtracting from total sum/count). All of this can be done with things like fenwick/segtree/treap etc. Using these 4 values, you can get the answer with math. Now, how to solve for tree case? Some standard ways to solve it:
Persistent segtree bash (using persistence to store the sum & count from the root to each node, then using the fact that sum/count from u->v = root->u + root->v — 2*root->lca(u,v).$$$O((N+Q)log C)$$$. Can be sped up to $$$O((N+Q)logN)$$$ with discretization offline.
Mo's algorithm on tree (using Euler tour to convert the tree queries to line query + LCA, then using Mo's to answer the queries) $$$O((N+Q)\sqrt{N}logN)$$$ <- This complexity is quite slow XD. Can be sped up to $$$O((N+Q)\sqrt{N})$$$ probably
Notice that we have $$$O(N\sqrt N)$$$ modifications but only $$$O(Q)$$$ queries. So don't use log DS but apply square root decomposition to strike a balance(discretization needed).
$$$O(\sqrt N)$$$ to query and $$$O(1)$$$ to modify. Total complexity is $$$O((N+Q)\sqrt N)$$$.
Nice trick :)
Problem link?
asked in today's leetcode contest weekly contest 361
you can select an edge and increase or decrease its weight by 1. If you are talking about today's leetcode contest question 4 then you read the question wrong. You can change the weight of edge toany valuerather than increasing or decreasing it by1.it will be done by same method bro it is almost similar though :)
Kind of but the constraints are also important.
1<=n<=1e4and1<=w<=26where n is number of nodes and w is weight of edges, which allows for simpler approaches to work also and doesn't require ds like segment tree or such. Also the answer would be different if the operation is increase or decrease by 1 rather than change it to any value.It is a OA question of Hackerearth Contest by Globalization partners and the contest is ended and there were also additional constraints on weight , weights can be upto 26 only so my approach was just to store all the weight values(coming in the path from that node to root ) for every node then we can apply binary lifting for finding lca of two nodes and take the union of both like for 3 and 2 and suppose lca of both 3 and 2 is 4 and then we will take union of these two arrays and subtracting the array of 4 and simply we can brute force for the answer as the chosen weights can be upto (1 to 26)
Bro! you did any pre-processing or did this for each query individually?
check this https://leetcode.com/submissions/detail/1039356326/