orz

Bro, note that $$$Q\le 2\times10^7$$$

I think the tutorials means that those intervals are illegal.

An interval is illegal means that if $$$s_i\in[l, r]$$$, $$$i$$$ will not be counted into $$$f(x)$$$.

3q

[deleted]

[deleted]

Thanks, dude!

It's so sad for me since I cannnot solve some easy problems recently. As you can see, my rating and rank dropped during some previous contest. I'm also looking for some solutions. :(

I don't think this solution should be hacked. At least it showed an important way to improve the time complexity($$$O(\frac{1}{\omega})$$$). In my point of view, various solutions are also important and inspiring.

Though my rating dropped after the contest, I think it's a pretty good round.

Because it made me realize my poor ability in dp on tree :)

Could you plz explain why starting from 1 will get WA, while starting from n can find out the correct answer? I didn't get that :(

Actually, I made some testcases that can hack my program(starting from 1). But I don't know why it can be correct to start from n.

It should be [1900, tourist].

DELETED

I agree with you.

btw, it's common in China. LOL

Pardon?

Yeah, thank you, very clear.

Sorry for the late reply and my poor English.

Let's try to calculate the answer from the different weights.

For every kind of weight of an edge, try to figure out the value that this kind of edge contributes to the answer.

For example, in the following illustration, the contribution of edges weigh $$$2$$$ is $$$3\times1+3\times3=10$$$.

Why?

If we cut the every edge weighs $$$2$$$(red edges), we will get $$$3$$$ new trees.

For the edge $$$(6, 7)$$$, the new trees it connected are $$$4,5,6$$$ and $$$7$$$, so answer will add $$$1\times3$$$. Because for the paths from $$$u$$$ to $$$v$$$, where $$$u=4,5,6$$$ and $$$v=7$$$, the value $$$2$$$ will definitly appear exactly once.

For the same reason, edge $$$(4, 1)$$$ will contribute $$$3\times 3$$$ to the answer.

Obviously, the edges with different values can't influence each other, so You can calculate the different values of edges partly.

Here is how to calculate the answer of edges with same value.

Firstly, get the 'bracket order' of the tree. Let $$$L[u]$$$ and $$$R[u]$$$ be the begining and ending indices of $$$u$$$ in the 'bracket order'.

It's another kind of Euler Tour of Tree. Instead of output the number as soon as you visit a node, you will output the number only when you first visit the node or finish visiting the node.

I don't know how to translate 'bracket order' to English since I'm Chinese and my English is poor. For example, the 'bracket order' of the tree in the illustration is $$$\texttt{4 5 5 6 7 7 6 1 2 2 3 3 1 4}$$$, hope you can understand what I want to express from the example. Or maybe you can see my code in the end.

Then, for a tree, cut the edges in dfs order and split the subtrees out, and cut the edges in a subtree recursively.

function Cut(int CurL, int CurR, int &CurE):
    for CurE in [CurL, CurR]:
        cur_real_size -= size[v]
        append value of Cut(L[v], R[v], CurE) to real_subtree_size
    for val in real_subtree_size:
        answer += val * cur_real_size
    return cur_real_size
// edges are sorted in dfs order, so an edge have a dfs order, you can judge whether the edge is in the subtree or not.
// CurE means the index of the edge you are visiting

When you cut the subtree recursively and update CurE, CurE is increasing and always less than $$$O(n)$$$. So the time complexity is $$$O(n)$$$.

You can see my submission to have a better understanding, I think it's quite short: 158222894

Actually I don't know whether it's violation of rules for me to type the solution in the comment. If it is, please tell me and I will delete my comment at once.

Apologise again for my poor English.

If you like, I can give another solution to you.

But it solves the problem from an aspect differ from the tutorial.

congratulations

I think your graph is so inspiring, too.

If someone is going to be an expert, it must be you. XD

lol

got it, thx

But it seems that the number of edges is $$$O(n^2)$$$..?

Awesome! Thank you very much

I only have an $$$O(n^2)$$$ algorithm. For each loop, choose one node as the starting point, then judge whether the dfs order on the tree is same as the loop's order.

Yes, but I have no idea how to solve it on the tree