DreamGrid has just found two trees, both consisting of n vertices, in his right pocket. Each edge in each tree has its own weight. The i-th edge in the first tree has a weight of aia_iai, while the i-th edge in the second tree has a pair of weight, denoted by . Let 1u{}^1!u1ube the u uu-th vertex in the first tree, and 2u{}^2!u2ube the u uu-th vertex in the second tree. Let E1mathbb{E}_1({}^1!v)E2be the set containing the indices of all the edges on the path between the u uu-thand thev vv-thvertex in the second tree. Define the following values: Amin=min{ak∣k∈E1}A_{min}({}^1!v)}Bmax=max{bk∣k∈E2} Cmax=max{ck∣k∈E2}C_{max}({}^2!j))Amin≥min. Please help DreamGrid figure out all the valid indices. You may have seen this problem before, but this time we need you to have an OOOsolution, or it may not pass.
DreamGrid has just found two trees, both consisting of n vertices, in his right pocket. Each edge in each tree has its own weight. The i-th edge in the first tree has a weight of aia_iai, while the i-th edge in the second tree has a pair of weight, denoted by (bi,ci)(b_i, c_i)(bi,ci). Let 1 u{}^1!u1u be the u u u-th vertex in the first tree, and 2 u{}^2!u2u be the u u u-th vertex in the second tree. Let E1(1 u,1 v)mathbb{E}_1({}^1!u, {}^1!v)E1(1u,1v) be the set containing the indices of all the edges on the path between the u u u-th and the v v v-th vertex in the first tree. Similarly, let E2(2 u,2 v)mathbb{E}_2({}^2!u, {}^2!v)E2(2u,2v) be the set containing the indices of all the edges on the path between the u u u-th and the v v v-th vertex in the second tree. Define the following values: Amin(1 u,1 v)=min{ak∣k∈E1(1 u,1 v)}A_{min}({}^1!u, {}^1!v) = min{a_k | k in mathbb{E}_1({}^1!u, {}^1!v)}Amin(1u,1v)=min{ak∣k∈E1(1u,1v)} Bmax(2 u,2 v)=max{bk∣k∈E2(2 u,2 v)}B_{max}({}^2!u, {}^2!v) = max{b_k | k in mathbb{E}_2({}^2!u, {}^2!v)}Bmax(2u,2v)=max{bk∣k∈E2(2u,2v)} Cmax(2 u,2 v)=max{ck∣k∈E2(2 u,2 v)}C_{max}({}^2!u, {}^2!v) = max{c_k | k in mathbb{E}_2({}^2!u, {}^2!v)}Cmax(2u,2v)=max{ck∣k∈E2(2u,2v)} As DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index i(1≤i≤n)i (1 le i le n)i(1≤i≤n) is good, if for all 1≤j≤n1 le j le n1≤j≤n and j≠ij ne ij=i, Amin(1 i,1 j)≥min(Bmax(2 i,2 j),Cmax(2 i,2 j))A_{min}({}^1!i, {}^1!j) ge min(B_{max}({}^2!i, {}^2!j), C_{max}({}^2!i, {}^2!j))Amin(1i,1j)≥min(Bmax(2i,2j),Cmax(2i,2j)). Please help DreamGrid figure out all the valid indices. You may have seen this problem before, but this time we need you to have an O(NlogN)O(N log N)O(NlogN) solution, or it may not pass.
