Oh, I realized something just a few minutes ago

I guess you are same to me : observe that $$$b$$$ will be sorted, and we will find a way to put $$$b[i]$$$ in $$$a$$$. But we actually skip a few things.

Let $$$best[i]$$$ is the best position for $$$b[i]$$$ to put in array a, which mean : if we put $$$b[i]$$$ at $$$best[i]$$$, the numbers inversion of $$$b[i]$$$ for $$$a$$$ will be minimum (notice that we not consider the numbers inversion in array $$$b$$$)

assume that we find a pair $$$i$$$ and $$$j$$$ such that $$$b[i]$$$ < $$$b[j]$$$ and $$$best[i]$$$ $$$ \gt $$$ $$$best[j]$$$, it will be a contradition. Why ? Because why don't move $$$best[j]$$$ to $$$best[i]$$$ ? Yup, by answer this question, we will get what we want. (why don't you write some example on paper to see something ?)

The important is : $$$best[i]$$$ $$$ \lt =$$$ $$$best[i + 1]$$$ (for sorted $$$b$$$)

I guess it relate to dp optimize technique (you can see it here : https://codeforces.me/blog/entry/8219 )

We want to prove $$$best[i] \lt = best[i + 1]$$$ where $$$best[i]$$$ is the best position to put $$$b[i]$$$.

But how can we prove it? I don't know...

that's so hurt, guy. I just want to archive and share...

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

Thanks for amz explain. I realize that I had some missunderstand in the way we calc $$$P(reach\ A\ before\ B)$$$

This's exactly what in my mind one day ago: let $$$s = ...a...b...$$$ where $$$a$$$ and $$$b$$$ is node $$$a$$$ and node $$$b$$$, "$$$...$$$" mean some node between them which we chose them in exactly that order, or in other word, $$$s$$$ is state represent what we chose (exact in this order) I think $$$P(reach\ A\ before\ B)$$$ (or $$$P(A \lt B)$$$) must be calculate in this way :

$$$P(A \lt B) = \sum_{\substack{all\ s\ which\ a \lt b}} P(s)$$$

But unfortunately, it's wrong (may be, or I still missunderstanding)

$$$P(A) = \sum_{\substack{all\ B[i]\ \subseteq\ A}} P(B[i])$$$ if and only if all $$$B[i]$$$ are distinct

Can you explain this?

Assume $$$X$$$ is initially node we chose. Then define a function $$$g$$$ :

$$$g[a][b][STATE]$$$ = probability to reach a before b while state of the tree we reach is $$$STATE$$$, and $$$a$$$, $$$b$$$ is length of path.

follow the image, I can see : $$$g[a][b][STATE_x] = \frac{1}{4} (g[a][b][STATE_d] + g[a][b][STATE_e] + g[a — 1][b][closer_a] + g[a][b — 1][closer_b])$$$

It can easy see that the probability can change. Or I wrong in some where?

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

oh, I was realize that, we only can make bamboo tree or cycle (only 1 cycle) with this graph, how stupid!

Now i understand how to solve, thank u!

huhmm...

I still don't understand the solution above(why it's correct), but I will think about that and try by my best thank u!

// the problem is in a Vietnamese website and I was change it (a little bit) to this question

n = 2

your solution is 2 but correct answer is 1

// but in anyway, thank you for reading and answer my question

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

here : https://oj.vnoi.info/problem/vosgame but it's a vietnamese web

I think math problem can be too difficult to solve if we don't think "right way".

Problem B is an example. d = a[i] — a[i — 1] can be easily to see that it only equal c or c — m. But if you think about "if a[1] = 0, What will happen?". Yeah, a[2] = c. It lead me to try -a[1] to all a[i] and got a big stuck in B. There is an exit for math problem? What thing I can do to improve that?

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

Can you explain why does C[x][j]+C[y][j+1] ≤ C[y][j]+C[x][j+1] is a contradiction in < case? May be C[i][j] has a special property?

thank you!

Let x[i] = log2(a[i])

then b[i] = 2^x[i]. It can be prove that sum of all 2*|a[i] — b[i]| always <= S

This problem can be extend to k*|a[i] — b[i]| <= S. It will be so funny XD

another approach for B is 2^k

I solved D and I didn't know how I can. Did someone in me for a while? After read editorial, i was confusing:((((((

Here is a another clean approach for Tree Distances II which I also like that!

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <math.h>
#include <iomanip>
#include <queue>
#include <map>
#include <unistd.h>

#define LL long long
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define X first
#define Y second
#define pb(a) push_back(a);
#define pii pair<int, int>
#define pLi pair<LL, int>
#define piL pair<int, LL>
#define pLL pair<LL, LL>
#define ar array

using namespace std;
const int mxn = 2e5 + 5;
LL dp[mxn], node[mxn], n;
vector<int> a[mxn];

void dfs (int p, int u)
{
    for (int v : a[u]) if (v != p)
    {
        dfs(u, v);
        dp[u] += node[v] + dp[v];
        node[u] += node[v];
    } ++node[u];
}

void dfs2 (int p, int u)
{
    dp[u] += (dp[p] - dp[u] - node[u]) + n - node[u];
    for (int v : a[u]) if (v != p) dfs2(u, v);
}

int main()
{
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);
    cin >> n;
    REP(i, 2, n)
    {
        int u, v;
        cin >> u >> v;
        a[u].pb(v); a[v].pb(u);
    }
    dfs(0, 1);
    for (int v : a[1]) dfs2(1, v);
    REP(i, 1, n) cout << dp[i] << ' ';
}

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

That works! Thank you very much. I was checked it as careful as I can. But it still has a big mistake. Thank you again!

me too

Someone please help me with the tutorial for E.

I don't understand because may be the code was not follow the tutorial