B01T - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Danny Boy
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

2526

PREREQUISITES:

Intermediate Value Theorem

PROBLEM:

You have a tree of N vertices rooted at vertex 1, where N is even. The i-th vertex has a binary value A_i written on it (i.e, each A_i is either 0 or 1).

A tree is said to be balanced if and only if the number of zeros written on its vertices equals the number of ones written on its vertices.

You can select some disjoint subtrees and flip the values on them (i.e, make all 0’s into 1’s and all 1’s into 0’s). Formally, you can pick any subset (possibly empty) of vertices \{v_1, v_2, \ldots, v_k\} such that v_i is not an ancestor of v_j for i \neq j, and flip the value of A_x for every vertex x that is contained in the subtree of some v_i.

Find a way of performing this operation that makes the entire tree balanced. It can be proved that the solution always exists.

EXPLANATION:

Let’s order the vertices by non-decreasing heights, and call this order O = [O_1, O_2, \dots, O_N], where obviously O_1 = 1. We have this following observation:

  • Taking any suffix of O and inverting all nodes in this suffix is equivalent to inverting some disjoint subtrees.

To see how this observation work, suppose we are inverting the suffix O_i, O_{i + 1}, \dots, O_N. Let the height of O_i be d. Essentially, we are inverting all nodes with height at least d + 1, as well as some nodes with height d. This corresponds to inverting the subtree of those d-height nodes, as well as some subtrees of some d + 1-height nodes that is not covered by those d-height nodes.

With this observation, we create a new array P, where P_i is equal to the amount of 1-value nodes minus the amount of 0-value nodes (for sake of simplicity, we call this the balance value) among O_1, O_2, \dots, O_i. We can calculate P_i pretty easily (it’s sort of a prefix sum).

Note that initially, the balance value of the whole tree is just P_N, and we want this balance value to be 0. Inverting any suffix O_i, O_{i + 1}, \dots, O_N will change the balance value to P_{i - 1} - (P_N - P_{i - 1}) = 2 \cdot P_{i-1} - P_N, so we want to choose some i such that P_{i - 1} = \frac{P_N}{2}, then invert the suffix O_{[i..N]}. Luckily, using the intermediate value theorem, we can prove that there always exist such an i, and therefore the problem is solved.

TIME COMPLEXITY:

Time complexity is O(N) per test case if we use BFS to generate the order.

SOLUTION:

Setter's Solution
##include <bits/stdc++.h>
#define ll long long
#define int long long
#define fi first
#define se second
using namespace std;
void db() {cout << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
const int N = 3e5 + 1, mod = 998244353;
ll inf = 1ll << 60;
int d[N], par[N]{};
vector<int> g[N];
void dfs(int u, int p){
    for (int i : g[u]) if (i != p){
        d[i] = d[u] + 1;
        par[i] = u;
        dfs(i, u);
    }
}
void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) g[i].clear();
    int a[n + 1], sum = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i] == 0 ? -1 : 1;
    }
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<pair<int, int>> v;
    dfs(1, -1);
    for (int i = 1; i <= n; i++) v.push_back({d[i], i});
    sort(v.begin(), v.end());
    int suf = 0, tar = n;
    for (int i = n - 1; i >= 0; i--){
        suf += a[v[i].se] == 0 ? -1 : 1;
        if (sum - suf * 2 == 0) {
            tar = i;
            break;
        }
    }
    bool flag[n + 1]{};
    for (int i = tar; i < n; i++) flag[v[i].se] = 1;
    vector<int> ans;
    for (int i = 1; i <= n; i++) if (flag[i] and !flag[par[i]]) ans.push_back(i);
    cout << ans.size() << '\n';
    for (int &i : ans) cout << i << ' ';
    cout << '\n';
}
signed main(){
    file;
    int t = 1;
    cin >> t;
    while (t--) solve();
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,m;
string s;
int a[300001];
vector<int>adj[300001];
int ptr=0;
int st[300001],en[300001];
int p[300001];
vector<int>ans;
void dfs(int id,int pp){
	st[id]=++ptr;
	p[ptr]=p[ptr-1]+a[id];
	for(auto c:adj[id]){
		if(c==pp) continue;
		dfs(c,id);
	}
	en[id]=ptr;
}
void solve(int id,int p,int ql,int qr){
	if(ql<=st[id] && en[id]<=qr){
		ans.push_back(id);return;
	}
	if(st[id]>qr || en[id]<ql) return;
	for(auto c:adj[id]){
		if(c==p) continue;
		solve(c,id,ql,qr);
	}
}
void solve(){
	cin >> n;ptr=0;ans.clear();
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		adj[i].clear();
	}
	for(int i=1; i<n ;i++){
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1,0);
	for(int i=0; i<n ;i++){
		int res=p[i]+(n-i)-(p[n]-p[i]);
		if(res==n/2){
			solve(1,0,i+1,n);
			cout << ans.size() << '\n';
			for(auto c:ans) cout << c << ' ';
			cout << '\n';
			return;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n);
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i < n; i++) {
            int u, v; cin >> u >> v; u--; v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // return order, parent
        auto BFS = [&](int src) {
            vector<int> par(n, -1), ord;
            // src is never chosen as a subtree, so we are safe to set par[src] = src
            par[src] = src; ord.push_back(src);
            for (int i = 0; i < n; i++) {
                int u = ord[i];
                for (int v : adj[u]) {
                    if (par[v] == -1) {
                        par[v] = u;
                        ord.push_back(v);
                    }
                }
            }
            return make_pair(ord, par);
        };
        auto [ord, par] = BFS(0);
        vector<int> prf(n);
        for (int i = 0; i < n; i++) {
            prf[i] = (i == 0 ? 0 : prf[i - 1]) + (a[ord[i]] == 0 ? 1 : -1);
        }
        for (int i = 0; i < n; i++) {
            if (prf[i] == prf[n - 1] / 2) {
                vector<bool> mrk(n);
                for (int j = i + 1; j < n; j++) {
                    mrk[ord[j]] = true;
                }
                vector<int> ans;
                for (int u = 0; u < n; u++) {
                    if (mrk[u] && !mrk[par[u]]) {
                        ans.push_back(u + 1);
                    }
                }
                cout << ans.size() << '\n';
                for (int v : ans) {
                    cout << v << " ";
                }
                cout << '\n';
                break;
            }
        }
    }
}
5 Likes

What is wrong with my approach?

My approach:
(I am taking only 1 operation with multiple vertices.)
(I am trying to do search like in segment tree)

WLOG assume n0 >= n1 (n0 = number of 0s, n1 = number of 1s)

Calculate number of 0s and 1s in subtree of each vertex in vector of pair using DFS1

We want to decrement n0 by n0-n/2, store in variable decr
I am using DFS2:

I am iterating through child of vertex, If we choose this vertex then we can decrease 0 by cnt[v].fi-cnt[v].se = can, if can < 0 reject it,
if can <= decr, then add this vertex to our chosen set and decrease decr by can(decr - = can), and continue the search in other subtree with new decr value.
If can > decr, the we can do our task by choosing some vertex in this subtree only and we don’t need other subtree, so continue the search in this subtree with same decr value

Submission link : Solution: 64902763 | CodeChef

Can someone tell me what is wrong with my approach?

Approach:
Doing a DFS from the root and making the first n/2 vertices visited as 0 and then making the the last n/2 vertices visited to be 1.
If a vertex does not equal to what it is supposed be(first n/2 = 0, last n/2 = 1), then we are flipping it and transferring that information(that its subtree needs to be flipped) to its children.
Trying to do the dfs from the root of the tree because changing a leaf and then changing a level above the leaf nodes would alter the state of the leaf node; but changing the levels above leaf nodes and then changing leaf nodes would allow us to persist those changes in the leaf nodes, giving more control to the desired tree structure.

Submission Link : Solution 64935583 | Codechef

if i didn’t get your idea wrong then i think you probably missed out in the problem statement. You need to flip disjoint subtrees. But you are flipping on the basis of first n/2 then last n/2 without taking care of this criterion.

2 Likes

How to deduce change in balance is Pi-1-(PN-Pi-1) ? And how to use intermediate value theorem to prove that such a solution exists?

1 Like

It’s almost correct, the only thing you need to add is to check the max value in the subtree which can be subtracted instead of finding the vertex with can<=decr. It can be the case for a certain vertex that can<=decr but there may exist some other node whose can2<=decr and can2>can, in this case it would be better to choose the can2 node.
You can check my submission, with the same approach (Code is readable) : Solution: 64934654 | CodeChef

1 Like

Why does this solution always work?

It would be better to choose can2 but we don’t need to minimize operations. Even if we choose can1, my solution should work:
Say, can1 < can2 <= decr
If use can1, new value of decr is (decr-can1) > 0:
case1: can2 <= decr-can1, we can easily take it.
case2: can2 > decr-can1, we can make search in this subtree.

yes you are right…seems like i misread the question and didn’t account for the disjoint subtree condition. Thanks a lot!!

Wait can2 node is in the subtree of can1 node, so how can you take both of them?

1 Like

Ah got you bro, Thank you so much bro.

Balance on left is P[i-1] so on right is P[N]-P[i-1]. Now we we are inverting the suffix, so new balance on right is -(P[N]-P[i-1]). Total balance is sum of left and right

Balance after taking no nodes : P[0] = 0;
Balance after taking all nodes: P[N]
Required balance: P[N]/2
At each step, the absolute change in value is 1, So we’ll surely reach P[N]/2 somewhere before i=N

Oh okay . Thanks…

I just want to confirm if one can solve this problem like this:
Approach:
if 1’s are greater than 0’s then choose the node having 1 and flip this whole node’s subtree once and flip all its child subtree once so that all its child subtree is flipped twice so that their child subtree value remains the same and only the current nodes value change to 0.
vice-versa.

No, you can’t do that. First you will need to select some subtrees to flip (must be disjoint with each other)

Oh! thank u…

can some one please explain me why are we also taking this
if(flag[i] and !flag[par[i]])
why !flag[par[i]] ?
we are just flipping from O(i…n) right? then why this?
why are we finding the parent?

Also can someone explain me what does disjoint subtree mean here like when you sort one the basis of height in non decreasing order then how can O1 = 1?
non decreasing means all nodes from leaf nodes to root. Right?

So, I am not able to understand the problem. Please help me explain what is disjoint subtree here.


Here, these cross marks are the set of vertices we can choose since we can’t find any pair (i!=j) where a[i] is the ancestor of a[j]. Is this understanding correct, as per the problem statement?

I still don’t get it, what do disjoint subtrees actually means?

May you please explain implementation in editorial through steps?
I can’t understand it