Need help for some problems
Difference between en1 and en2, changed 825 character(s)
I've encountered some interesting problems but I couldn't solve them. I really need some help.↵
<br><br>↵
<strong>First problem</strong> is: Given 3 integers <strong>N</strong>, <strong>M</strong>, <strong>X</strong> (1 <=
N, M <= 10<sup>5</sup>, 1 <= X <= m<strong>N</strong>, <strong>M</strong> <= 10<sup>5</sup>, 1 <= <strong>X</strong> <= <strong>M</strong>). Calculate the number of ways to create <strong>nN</strong> segments [L<sub>1</sub>, R<sub>1</sub>], [L<sub>2</sub>, R<sub>2</sub>], …, [L<sub>nN</sub>, R<sub>n</sub>] (Li <= Hi) such that they satisfy two conditions:↵
<ul>↵
<li>↵
there is no <em>i</em> and <em>k</em> (i != k) that L<sub>i</sub> <= L<sub>k</sub> <= H<sub>k</sub>
N</sub>] (Li <= Hi) such that they satisfy two conditions:↵
<ul>↵
<li>↵
there is no <em>i</em> and <em>k</em> (i != k) that L<sub>i</sub> <= L<sub>k</sub> <= H<sub>k</sub> <= H<sub>i</sub>↵
</li>↵
<li>↵
There is at least one segment which has L<sub>i</sub> = <strong>X</strong>↵
</li>↵
</ul>↵
Two ways are different if there exists <em>j</em> such that segment <em>j</em> in two ways are different.↵
<br><br>↵
<strong>Second problem</strong> is: Given a tree with 4 nodes 1, 2, 3 and 4. Node 1 is root. Nodes 2, 3 and 4 are leaf nodes. <strong>Diameter of the tree</strong> is the longest path on the tree. We have <strong>Q</strong> queries (1 <= <strong>Q</strong> <= 5 * 10<sup>5</sup>). For each query, we are given a leaf node <strong>v</strong> (1 <= v
<= H<sub>i</sub>↵
</li>↵
<li>↵
There is at least one segment which has L<sub>i</sub> = s↵
</li>↵
</ul>
trong>N</strong>, <strong>N</strong> is the number of nodes in the tree). Then we add two new nodes N + 1 and N + 2 to the tree, create two edges (v, N + 1) and (v, N + 2). Output after each query is the diameter of the tree.↵
<br><br>↵

History

Revisions Rev. Lang. By When Δ Comment
en2 DooIt 2015-08-10 12:35:13 825 (published)
en1 DooIt 2015-08-10 11:58:14 714 Initial revision (saved to drafts)