Another (IMO very nice) construction for Villagers — Maximum: Do dfs on the tree and sort the vertices by dfs preorder. Let $$$ord[i]$$$ be the $$$i$$$-th vertex we visit in the dfs. Then move villager $$$ord[i]$$$ to house $$$ord[(i + \frac{n}{2}) \; mod \; n]$$$. It‘s not hard to prove that this is maximal.

Can someone please share his implementation for problem A ?

I have an alternative solution to problem B1.

First, we can see that we can choose a subset S of x nodes, such that 2 <= x <= N, and match everyone in this set with another such that no one ends in the position that it had, we can see that in the optimal strategy each edge in the smallest subtree that contains all nodes in S will be counted twice, so the optimal strategy will be always sort by its dfs order and match S[i] with S[(i+1)%|S|] for each i from 0 to |S|-1 (shift right by 1).

Then we can reduce our problem to cut the tree into subsets of nodes, and add their consecutive distances, it will be always optimal select subsets which forms a connected subtree, otherwise we add some edge more than twice. Its also optimal to select as much subsets as possible, because having k of them we will use only n — k — 1 edges from the tree, and each edge will be used twice.

Then we can do the following greedy algoritm: Choose one node and color it black, its adyacents white and so on, like in a bipartite assignment. Then we run dfs from any node (node 1 for simplicity) and when we found a edge such that any of its endpoints are unused, create a new subset with this two nodes and mark them as used, and keep doing this, finally, run a multi-source bfs and add unmarked nodes to some adyacent subset, this algorithm is optimal because the matching that we found is maximal, and because no single-nodes can be in a subset, the smallest size of valid a subset is 2, then the best answer is the maximum matching.

You can see my code here for a better understanding

///

void dfs_color(int u,int c){ color[u] = c; for( auto v : g[u] ) if( !color[v] ) dfs_color(v,c%2+1); }

void dfs(int u,int p){ for( auto v : g[u] ) if( v != p ) dfs(v,u); for( auto v : g[u] ) if( v != p ) if( color[u] != color[v] && ( res[u] == 0 && res[v] == 0 ) ){ res[u] = res[v] = ++cnt; q.push(u); q.push(v); } }

void bfs(){ while( !q.empty() ){ int u = q.front(); q.pop(); for( auto v : g[u] ){ if( !res[v] ){ res[v] = res[u]; q.push(v); } } } } ///

///inside main cin >> n;

for(int i=1; i<n; i++){
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
}

dfs_color(1,1);

dfs(1,1);

bfs();

for(int i=1; i<=n; i++)
    w[res[i]].pb(i);

int min_ans = 0;
for(int i=1; i<=cnt; i++){
        min_ans += ( ( (int)w[i].size() - 1 ) * 2 );
    for(int j=0; j<w[i].size(); j++){
        ans[w[i][j]] = w[i][(j+1)%w[i].size()];
    }
}

cout << min_ans << '\n';
for(int i=1; i<=n; i++)
    cout << ans[i] << ' ';
cout << '\n';

///

can anyone please explain why in the editorial of problem A do we have a_u*a_v=-1 ?

I wonder why my solution to problem C got accepted. While I had almost finished the implement of my first thought, I found that I didn't consider the case that the mutation table of a gene may contain itself and I couldn't find a good order to DP. Then I thought that this case may not occur too much times, so I just iterated 10 times to get better answer, and surprisingly I got AC. I even can't prove it!

Does anyone have similar solution or idea about this? This is my AC solution

In problem A, Why is it giving wrong answer for this submission on test 6?

The sum of values of vertices is same in jurys answer and my answer.

I finished problem A in a different manner, and sometimes it doesn't even consider the median of b's. I wish someone could show me the proof that the median is good (if you know it, please reply my comment. Very grateful already!). I found my way more intuitive (of course, because I thought of it :P), and I'll describe it.

So we ended up with lots of $$$f(x) = ax+b$$$ functions, where $$$a \neq 0$$$ (if $$$a = 0$$$, throw it away, for it's a constant). This way, there are only two cases:

• if $$$a < 0$$$, then for every $$$x > -b/a$$$, $$$f(x) < 0$$$, and for every $$$x < -b/a$$$, $$$f(x) > 0$$$.

• if $$$a > 0$$$, then for every $$$x > -b/a$$$, $$$f(x) > 0$$$, and for every $$$x < -b/a$$$, $$$f(x) < 0$$$.

So I put in a vector every pair($$$-b_i/a_i$$$, $$$i$$$) and sorted it. My observation was that, between two consecutive $$$x$$$'s in the vector, the sum of the absolute value of the functions is a linear function itself. So the best answer would be one of the endpoints of this interval. And the only function that stop behaving the way it was when we reach a new $$$x$$$ is the function responsible for this $$$x$$$. For example, suppose we are processing $$$a_ix+b_i$$$ and $$$a_i > 0$$$. So, before we process it, the real addition this function gives to the total is its reflection according to the x-axis — i.e, $$$-a_ix-b_i$$$. The moment we process its $$$x$$$, it gives us 0, of course. After it, the addition changes to $$$a_ix+b_i$$$. That's it.

Maybe I unconsciously did that median thing, but it isn't quite clear to me. Please someone provide a proof!