PROBLEM LINK:
Master Tree
Author: artha6391
Tester: anushka_nagar
Editorialist:giraj_12
Difficulty:
Medium
PREREQUISITES:
PROBLEM:
The Greatness of a tree can be found using the following function-
long long int Greatness(int N, int A[]){
long long int val = 0;
for(int i = 1; i < N; i++){
for(int j = i + 1; j <= N; j++){
if(a[i] < a[j]){val++;}
else{val–;}
}
}
return val;
}
Here N are the number of nodes in a tree and visiting order of the tree is passed as elements of the array.(Consider 1 based indexing).
Let G be a tree with N nodes numbered from 1 to N rooted at node 1. Find the Expected Greatness of all the valid BFS(Breadth First Search) of G.
QUICK EXPLANATION:
Consider any bfs ordering Q w.r.t node 1, now from the nature of function, consider two elements, Qi, Qj at same depth the contribution of value across all permutations will be 0, hence you just need to calculate the value of above function across different depths which can easily be done by range queries.
EXPLANATION:
To calculate the E[Greatness], first we try to prove that we need not take into account for pair values at same level, in bfs.
Let’s say two elements, Qi, Qj are at same depth, the number of bfs permutations in which Qi occurs before Qj = the number of permutations in which Qi occurs after Qj. Hence the value is incremented and decremented equal number of times i.e 0 contribution.
Why the number of permutations are equal?
My claim is half of all the valid possible orderings will have Qi visit before Qj and the other half will have Qi visit after Qj.
Firstly let us denote the number of children of each node i by di. Hence total possible bfs orderings are Πdi! (1 ≤ i ≤ n). If node Qi is to be visited before Qj we will also have to visit the ancestors of Qi not later than Qj. Let l be the lowest common ancestor (lca) of Qi and Qj and Pi, Pj be the immediate children of l such that Pi and Pj are ancestors of Qi and Qj respectively. There are dl! ways of visiting children of node l and we select 2 positions and force Pi before Pj there are
(dl*/2)∗(dl−2)! ways of doing so. No matter how we permute things now on other nodes we ensure Qi is always visited before Qj since we also assumed they have same depth as well. Now the number of such orderings is d1!∗d2!…(dl/2*)∗(dl−2)!…dn!. Which is nothing but half of all possible bfs orderings.
Do refer to the wikipedia link of bfs, if you want to understand why making such choice at lca ensured this.
Now the problem is simply reduced to calculate the function only across different depth level in bfs tree. One way to do this is first calculate depth of each node and store them. Now iterate the node in the order of depth. For some depth d, add number of elements less than curNode - number of elements greater than curNode which are less than depth d. Update the segment tree once you iterate over all the nodes at depth d.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <vector>
#define int long long
std::vector<int> type[200005];
void dfs(int u, int d, std::vector<int> Adj[], int p) {
type[d].push_back(u);
for(int j : Adj[u]) {
if(j == p)
continue;
dfs(j, d+1, Adj, u);
}
}
int bit[200009];
void add(int x) {
x += 1;
while(x < 200009) {
bit[x]++;
x += x&(-x);
}
}
int sum(int x) {
x += 1;
int ret = 0;
while(x > 0) {
ret += bit[x];
x -= x&(-x);
}
return ret;
}
signed main() {
int n;
std::cin >> n;
std::vector<int> Adj[n];
int dep[n];
for(int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--; v--;
Adj[u].push_back(v);
Adj[v].push_back(u);
}
dfs(0, 0, Adj, -1);
int ans = 0;
int k = 0;
for(int i = n-1; i >= 0; i--) {
for(int j : type[i]) {
ans += 2*sum(n-j) - k;
}
k += type[i].size();
for(int j : type[i]) {
add(n-j);
}
}
std::cout << ans << std::endl;
}
Tester's Solution
#include <iostream>
#include <vector>
#define int long long
std::vector<int> type[200005];
void dfs(int u, int d, std::vector<int> Adj[], int p) {
type[d].push_back(u);
for(int j : Adj[u]) {
if(j == p)
continue;
dfs(j, d+1, Adj, u);
}
}
int bit[200009];
void add(int x) {
x += 1;
while(x < 200009) {
bit[x]++;
x += x&(-x);
}
}
int sum(int x) {
x += 1;
int ret = 0;
while(x > 0) {
ret += bit[x];
x -= x&(-x);
}
return ret;
}
signed main() {
int n;
std::cin >> n;
std::vector<int> Adj[n];
int dep[n];
for(int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--; v--;
Adj[u].push_back(v);
Adj[v].push_back(u);
}
dfs(0, 0, Adj, -1);
int ans = 0;
int k = 0;
for(int i = n-1; i >= 0; i--) {
for(int j : type[i]) {
ans += 2*sum(n-j) - k;
}
k += type[i].size();
for(int j : type[i]) {
add(n-j);
}
}
std::cout << ans << std::endl;
}
Editorialist's Solution
#include <iostream>
#include <vector>
#define int long long
std::vector<int> type[200005];
void dfs(int u, int d, std::vector<int> Adj[], int p) {
type[d].push_back(u);
for(int j : Adj[u]) {
if(j == p)
continue;
dfs(j, d+1, Adj, u);
}
}
int bit[200009];
void add(int x) {
x += 1;
while(x < 200009) {
bit[x]++;
x += x&(-x);
}
}
int sum(int x) {
x += 1;
int ret = 0;
while(x > 0) {
ret += bit[x];
x -= x&(-x);
}
return ret;
}
signed main() {
int n;
std::cin >> n;
std::vector<int> Adj[n];
int dep[n];
for(int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--; v--;
Adj[u].push_back(v);
Adj[v].push_back(u);
}
dfs(0, 0, Adj, -1);
int ans = 0;
int k = 0;
for(int i = n-1; i >= 0; i--) {
for(int j : type[i]) {
ans += 2*sum(n-j) - k;
}
k += type[i].size();
for(int j : type[i]) {
add(n-j);
}
}
std::cout << ans << std::endl;
}