BOI 2020 - Day 2 - Village (Maximum)

help
1

Hi, I got stuck on this problem recently. I’ve tried reading other solutions but can’t understand the general idea. Could anyone elaborate on how to solve the problem?

Here’s the link to CodeForces Online Mirror: Problem - B2 - Codeforces

Here’s the CF editorial: BOI 2020 Online Mirror — Day 2 Tutorial - Codeforces

I’m not getting why theoretical maximum is always possible, nor do I understand how to choose vertices to assign to each other as their resulting positions. Could anyone provide a bit more detailed solution explanation. Thanks.

EDIT: Here’s how I see things currently. We find centroid - so every villager changes his current state by changing the subtree it belongs to currently. Ok, but what do we do with the ceontrids? How do you cover case where N is odd? And how do you even decide where each vertex should move? I think I’m getting the intuition of why theoretical maximum is achievable, but still I have many unanswered questions. Thanks again to y’all that see this.

UPD: And another doubt I’m having - is there a way to create optimal arrangement by taking tree’s diameter and just swapping the vertices at the endpoints, then erasing them from the remaining graph. This greedy seems to work optimally to me (got no proof, which is why I’m asking), but I don’t think there’s a way to handle the case of odd number of vertices. Obviously this shouldn’t pass the whole task, but I’m wondering if it could pass as O(N^2 log N) for the second subtask.

Here’s William Lin’s solution to the problem, and I’ve seen most solutions to the same - how exactly is the k + (N + 2)/th discovered node alawys the answer for the kth one?

    #include <bits/stdc++.h>
    using namespace std;
     
    const int mxN=1e5;
    int n, s[mxN], dt, ds[mxN], ord[mxN];
    vector<int> adj[mxN];
    long long ans1;
     
    void dfs(int u=0, int p=-1) {
    	ord[u]=dt;
    	ds[dt++]=u;
    	s[u]=1;
    	for(int v : adj[u]) {
    		if(v==p)
    			continue;
    		dfs(v, u);
    		ans1+=min(s[v], n-s[v]);
    		s[u]+=s[v];
    	}
    }
     
    int main() {
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	
    	cin >> n;
    	for(int i=1, u, v; i<n; ++i) {
    		cin >> u >> v, --u, --v;
    		adj[u].push_back(v);
    		adj[v].push_back(u);
    	}
    	dfs();
    	cout << 2*ans1 << "\n";
    	for(int i=0; i<n; ++i)
    		cout << ds[(ord[i]+n/2)%n]+1 << " ";
    }

FINAL EDIT: Never mind, consider this as solved. I’ve just now found that the first comment of the editorial goes into details of why this soltuion is correct. I still haven’t figured everything out foramlly, but I can see why it’s true. :slight_smile: This seems to imply that my solution using diameter is possible as its vertices will always belong to different subtrees, but I still need to figure out where to place the last vertex in case of odd parity, if anyone has idea how to do this (or can prove it wrong), I’d appreciate it. :slight_smile: :slight_smile: :slight_smile: