Algorithm

Problem Name: Data Structures - Self-Driving Bus

In this HackerRank in Data Structures - Self-Driving Bus solutions

Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities.

The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true:

1. There is a path between every pair of cities which belongs to the subset.
2. Every city in the path must belong to the subset.

In the figure above, {2,3,4,5} is a connected subset, but {6,7,9} is not (for the second condition to be true, 8 would need to be part of the subset). Each self-driving bus will operate within a connected segment of Treeland. A connected segment [L,R] where 1 <= L <= R <= n is defined by the connected subset of cities

S = { x|x epsolutenot Z and L <= x <= R}.

In the figure above, [2,5] is a connected segment that represents the subset {2,3,4,5}.

Note that a single city can be a segment too.

Help Alex to find number of connected segments in Treeland.

Input Format

The first line contains a single positive integer, n. The n - 1 subsequent lines each contain two positive space-separated integers, ai and bi , describe an edge connecting two nodes in tree T.

Constraints

• 1 <= n <= 2 * 10**5
• 1 <= ai,bi <= n

• For 25% score: 1 <= n <= 2 * 10**5
• For 50% score: 1 <= n <= 10**4

Output Format

Print a single integer: the number of segments [L,R] , which are connected in tree T

Sample Input

``````3
1 3
3 2
``````

Sample Output

``5``

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define fprintf(...)

struct vertex {
struct vertex* parent;
int rank;
int count;
};

struct vertex* vfind(struct vertex *v) {
if (v->parent == NULL) return v;  // this is a disconnected one.
if (v->parent != v) {
v->parent = vfind(v->parent);
}
return v->parent;
}

struct vertex* vunion(struct vertex *x, struct vertex* y) {
struct vertex *xroot = vfind(x);
struct vertex *yroot = vfind(y);
if (xroot == yroot) return yroot;
// fix any uninitialized counts.
if (xroot->count == 0) xroot->count++;
if (yroot->count == 0) yroot->count++;

if (xroot->rank > yroot->rank) {
struct vertex* tmp = xroot;
xroot = yroot;
yroot = tmp;
}
// xroot is now the smaller tree if they're not the same.
if (xroot->rank == yroot->rank) {
yroot->rank++;
}
xroot->parent = yroot;
yroot->count += xroot->count;
return yroot;
}

struct edge {
int a, b;
};

int ecmp(const void*a_in, const void*b_in) {
const struct edge* a = a_in;
const struct edge* b = b_in;

if (a->b  <  b->b) return -1;
if (a->b > b->b) return 1;
if (a->a  <  b->a) return -1;
if (a->a > b->a) return 1;
return 0;
}

int ecmp_a(const void*a_in, const void*b_in) {
const struct edge* a = a_in;
const struct edge* b = b_in;

if (a->a  <  b->a) return -1;
if (a->a > b->a) return 1;
if (a->b  <  b->b) return -1;
if (a->b > b->b) return 1;
return 0;
}

// n * ack-1(n) algorithm; needs to be run n times for n^2 ack-1(n).  Not the best, but gets 50%.
int count_components1(int start, struct edge* edges, int ne, int n) {
if (ne == 0) return 1;
fprintf(stderr, "start: %d, ne %d, n %d\n", start, ne, n);
int max_components = n - start + 1;
struct vertex v[max_components];
memset(v, 0, sizeof(v));
int components = 1;
struct edge* le = edges + ne;
for (int maxv = start + 1; maxv  < = n; maxv++) {
struct vertex* join = NULL;
while (edges  <  le && edges->b <= maxv) {
if (edges->a >= start) {
join = vunion(&v[edges->a - start], &v[edges->b - start]);
fprintf(stderr, "Join: %d to %d, new count %d\n", edges->a, edges->b, join->count);
}
edges++;
}
if (join && join->count == maxv - start + 1) components++;
}
return components;
}

int count_components(int start, struct edge* edges, int ne, int n) {
if (ne == 0) return 1;
fprintf(stderr, "start: %d, ne %d, n %d\n", start, ne, n);
int max_components = n - start + 1;
struct vertex v[max_components];
memset(v, 0, sizeof(v));
int components = 1;
struct edge* le = edges + ne;
for (int maxv = start + 1; maxv  < = n; maxv++) {
struct vertex* join = NULL;
while (edges  <  le && edges->b <= maxv) {
if (edges->a >= start) {
join = vunion(&v[edges->a - start], &v[edges->b - start]);
fprintf(stderr, "Join: %d to %d, new count %d\n", edges->a, edges->b, join->count);
}
edges++;
}
if (join && join->count == maxv - start + 1) components++;
}
return components;
}

int old_main() {
int n;
scanf("%d\n", &n);
struct edge edges[n-1];
memset(edges, 0, sizeof(edges));
for (int i = 0; i  <  n-1; i++) {
int e1, e2;
scanf("%d %d\n", &e1, &e2);
if (e1  <  e2) {
edges[i].a = e1;
edges[i].b = e2;
} else {
edges[i].a = e2;
edges[i].b = e1;
}
}
qsort(edges, n-1, sizeof(struct edge), ecmp);
for (int i = 0; i  <  n-1; i++) {
fprintf(stderr, "Edge: %d %d\n", edges[i].a, edges[i].b);
}
int result = 0;
struct edge *ep = edges;
struct edge *lp = edges + n - 1;
for (int i = 1; i  < = n; i++) {
while(ep < lp && ep->a < i) ep++;
int cc = count_components(i, ep, lp - ep, n);
fprintf(stderr, "i: %d  cc: %d\n", i, cc);
result += cc;
}
printf("%d\n", result);
return 0;
}

struct node {
int nn;
// indexes of forward edges in the node.
// Edges always belong to the low node.
int first_edge;
int n_edges;
};

struct line {
int start_node;
int end_node;
};

struct segment_node {
int lazy;
int max_v;  // maximum value of any node below
int num_v;  // number of nodes with that maximum value
};

#define C1(i) ((i)*2+1)
#define C2(i) ((i)*2+2)

void propagate(struct segment_node* tree, int index, int start, int end) {
if (!tree[index].lazy) return;
if (start == end) {
// leaf, nothing to do;
tree[index].lazy = 0;
return;
}
fprintf(stderr, "Prop: %d v: %d\n", index, tree[index].lazy);
tree[C1(index)].lazy += tree[index].lazy;
tree[C2(index)].lazy += tree[index].lazy;
tree[C1(index)].max_v += tree[index].lazy;
tree[C2(index)].max_v += tree[index].lazy;
tree[index].lazy = 0;
}

// ns, ne = node start/end = recursion counter
// rs, re = input range start/end
// adds "v" to all nodes between rs and re.
// the segment tree is implicitly "complete", i.e. contains all integers in [ns, ne]
int treelim;
void update(struct segment_node* tree, int index, int ns, int ne, int rs, int re, int v) {
if (index >= treelim) exit(-1);
fprintf(stderr, "upd: i: %d ns,ne (%d %d) rs, re (%d %d), v %d\n", index, ns, ne, rs, re, v);
fprintf(stderr, "   prev max_v %d num_v %d\n", tree[index].max_v, tree[index].num_v);
propagate(tree, index, ns, ne);
if (ns == rs && ne == re) {
tree[index].max_v += v;
if (ns == ne) tree[index].num_v = 1;
tree[index].lazy += v;
return;
}
int mid = (ns + ne) / 2;
if (re  < = mid) update(tree, C1(index), ns, mid, rs, re, v);
else if (rs > mid) update(tree, C2(index), mid + 1, ne, rs, re, v);
else {
update(tree, C1(index), ns, mid, rs, mid, v);
update(tree, C2(index), mid + 1, ne, mid + 1, re, v);
}
// now up-propagate.
if (tree[C1(index)].max_v > tree[C2(index)].max_v) {
fprintf(stderr, "C1\n");
tree[index].max_v = tree[C1(index)].max_v;
tree[index].num_v = tree[C1(index)].num_v;
} else if (tree[C1(index)].max_v  <  tree[C2(index)].max_v) {
fprintf(stderr, "C2\n");
tree[index].max_v = tree[C2(index)].max_v;
tree[index].num_v = tree[C2(index)].num_v;
} else {
fprintf(stderr, "BB\n");
tree[index].max_v = tree[C1(index)].max_v;
tree[index].num_v = tree[C1(index)].num_v + tree[C2(index)].num_v;
}
fprintf(stderr, "upd done: %d max_v %d num_v %d\n", index, tree[index].max_v, tree[index].num_v);
}

int main() {
int n;
scanf("%d\n", &n);

struct node nodes[n];
struct edge edges[n-1];
int nl = 0;
memset(nodes, 0, sizeof(nodes));
memset(edges, 0, sizeof(edges));
for (int i = 0; i  <  n-1; i++) {
int e1, e2;
scanf("%d %d\n", &e1, &e2);
if (e1  <  e2) {
edges[i].a = e1;
edges[i].b = e2;
} else {
edges[i].a = e2;
edges[i].b = e1;
}
}
qsort(edges, n-1, sizeof(struct edge), ecmp);
for (int i = 0; i  <  n; i++) {
nodes[i].nn = i+1;
}
int cur_node = -1;
for (int i = 0; i  <  n-1; i++) {
fprintf(stderr, "Edge %d: %d %d\n", i, edges[i].a, edges[i].b);
if (edges[i].b - 1 > cur_node) {
for (int j = cur_node + 1; j  <  edges[i].b - 1; j++) {
// Make the zero-edge nodes have a "first edge" that makes sense
nodes[j].first_edge = i;
}
if (cur_node >= 0) {
nodes[cur_node].n_edges = i - nodes[cur_node].first_edge;
}
cur_node = edges[i].b - 1;
nodes[cur_node].first_edge = i;
}
}
fprintf(stderr, "n:%d, cur_node %d %d\n", n, cur_node, nodes[cur_node].nn);
nodes[cur_node].n_edges = n - 1 - nodes[cur_node].first_edge;
while (++cur_node  <  n) {
nodes[cur_node].first_edge = n - 1;
}
for (int i = 0; i  <  n; i++) {
fprintf(stderr, "Node: %d edges start at %d nedges %d\n", nodes[i].nn, nodes[i].first_edge, nodes[i].n_edges);
}
long result = 0;
treelim = 1<<((int)ceil(log2(n)) + 1);
struct segment_node stree[treelim];
memset(stree, 0, sizeof(stree));
for (int i = 0; i  <  n; i++) {
for (int j = nodes[i].first_edge; j  <  nodes[i].first_edge + nodes[i].n_edges; j++) {
update(stree, 0, 1, n, 1, edges[j].a, 1);
}
update(stree, 0, 1, n, nodes[i].nn, nodes[i].nn, nodes[i].nn);
fprintf(stderr, "Node %d max_v %d num_v %d\n", nodes[i].nn, stree[0].max_v, stree[0].num_v);
if (stree[0].max_v == nodes[i].nn) result += stree[0].num_v;
}
printf("%ld\n", result);
return 0;
}
``````
Copy The Code &

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
#include<unordered_map>
#include<cassert>
#include<cmath>

#define dri(X) int (X); scanf("%d", &X)
#define drii(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define driii(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define pb push_back
#define mp make_pair
#define rep(i, s, t) for ( int i=(s) ; i  < (t) ; i++)
#define fill(x, v) memset (x, v, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define why(d) cerr << (d) << "!\n"
#define whisp(X, Y) cerr << (X) << " " << (Y) << "#\n"
#define exclam cerr << "!!\n"
#define left(p) (p << 1)
#define right(p) ((p << 1) + 1)
#define mid ((l + r) >> 1)
typedef long long ll;
using namespace std;
typedef pair < int, int> pii;
const ll inf = (ll)1e9 + 70;
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 1000;

bool used[maxn];
int sz[maxn];//subtree sizes

int mark[maxn];
int tt = 0;

int maax[maxn];
int miin[maxn];
int goright[maxn];
int goleft[maxn];

int val[maxn];
int ST[4 * maxn];// an all-purpose ST: min, max, and sum!!
int query(int p, int l, int r, int i, int j){//sum query
if (l > j || r  <  i) return 0;
if (i <= l && r <= j){
return ST[p];
}
return query(left(p), l, mid, i, j) + query(right(p), mid + 1, r, i, j);
}
void update(int p, int l, int r, int i, int delta){
if (l > i || r  <  i) return;
if (l == r){
ST[p] += delta;
return;
}
update(left(p), l, mid, i, delta);
update(right(p), mid + 1, r, i, delta);
ST[p] = ST[left(p)] + ST[right(p)];
}
void buildtree(int p, int l, int r, bool m){
if (l == r){
ST[p] = val[l];
return;
}
buildtree(left(p), l, mid, m);
buildtree(right(p), mid + 1, r, m);
if (m) ST[p] = min(ST[left(p)], ST[right(p)]);
else ST[p] = max(ST[left(p)], ST[right(p)]);
}
vector < pair<int, pii>> blocks;
void decompose(int p, int l, int r, int i){
if (r  <  i) return;
if (l >= i){
blocks.push_back(mp(p, pii(l, r)));
return;
}
decompose(left(p), l, mid, i);
decompose(right(p), mid + 1, r, i);
}
void decompose2(int p, int l, int r, int i){
if (l > i) return;
if (r  < = i){
blocks.push_back(mp(p, pii(l, r)));
return;
}
decompose2(left(p), l, mid, i);
decompose2(right(p), mid + 1, r, i);
}

int find(int p, int l, int r, int x){
assert(ST[p]  <  x);
if (l == r) return l;
if (ST[left(p)] >= x){
return find(right(p), mid + 1, r, x);
}
return find(left(p), l, mid, x);
}

int find2(int p, int l, int r, int x){
assert(ST[p] > x);
if (l == r) return l;
if (ST[right(p)]  < = x){
return find2(left(p), l, mid, x);
}
return find2(right(p), mid + 1, r, x);
}

void dfs(int v, int p){
mark[v] = tt;
sz[v] = 1;
if (p == -1){
maax[v] = v; miin[v] = v;
}
else{
maax[v] = max(maax[p], v);
miin[v] = min(miin[p], v);
}

if (u == p || used[u]) continue;
dfs(u, v);
sz[v] += sz[u];
}
}

ll perform(int v, int n){
if (n == 1){
return 1;
}
//first, FIND the centroid.
dfs(v, -1);
int g = v; int p = -1;
while (true){
int w = -1;
if (h == p || used[h]) continue;
if (w == -1 || sz[h] > sz[w]) w = h;
}
assert(w != -1);//g should NOT be a leaf.
if (2 * sz[w]  < = n){
break;
}
p = g; g = w;
}
//g is the centroid.
tt++;
dfs(g, -1);
//here comes the HEART OF THE ALGORITHM.
int m = -800;
for (int l = g; l > 0; l--){
if (mark[l] != tt) break;
m = l;
}
int M = -800;
for (int r = g; r  <  maxn; r++){
if (mark[r] != tt) break;
M = r;
}
//Our working interval is m  < = i <= M.
rep(i, m, M + 1){
val[i] = miin[i];
//cout << miin[i] << " ";
}//cout << endl;
buildtree(1, m, M, true);
rep(i, m, M + 1){
if (miin[i]  <  i){
goright[i] = -inf;
continue;
}
blocks.clear();
decompose(1, m, M, i);
reverse(blocks.begin(), blocks.end());
while (!blocks.empty() && ST[blocks.back().first] >= i) blocks.pop_back();
if (blocks.empty()){
goright[i] = M;
}
else{
auto ee = blocks.back();
goright[i] = find(ee.first, ee.second.first, ee.second.second, i) - 1;
}
}
//rep(i, m, M + 1)cout << goright[i] << " "; cout << endl;
//now, goleft!
rep(i, m, M + 1) val[i] = maax[i];
//rep(i, m, M + 1) cout << maax[i] << " "; cout << endl;
buildtree(1, m, M, false);
rep(i, m, M + 1){
if (maax[i] > i){
goleft[i] = inf;
continue;
}
blocks.clear();
decompose2(1, m, M, i);
while (!blocks.empty() && ST[blocks.back().first]  < = i) blocks.pop_back();
if (blocks.empty()){
goleft[i] = m;
}
else{
auto ee = blocks.back();
goleft[i] = find2(ee.first, ee.second.first, ee.second.second, i) + 1;
}
}
//rep(i, m, M + 1) cout << goleft[i] << " "; cout << endl;
vector < pii> rs;
rep(r, m, M + 1){
if (goleft[r] != inf) rs.push_back(pii(goleft[r], r));
}
sort(all(rs)); reverse(all(rs));
rep(i, m, M + 1) val[i] = 0;
buildtree(1, m, M, true);//basically: just clear it.
ll ans = 0;
for (int l = m; l  < = M; l++){
//whisp(l, goright[l]);
while (!rs.empty() && rs.back().first == l){
update(1, m, M, rs.back().second, 1);
//cout << "update " << rs.back().second << "\n";
rs.pop_back();
}
//cout << query(1, m, M, l, goright[l]) << "\n";
ans += query(1, m, M, l, goright[l]);
}
used[g] = true;
vector < pii> ls;
if (used[u]) continue;
ls.push_back(pii(u, sz[u]));
}
for (pii x : ls){
ans += perform(x.first, x.second);
}
return ans;
}

int main(){
if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
dri(n);
rep(i, 1, n){
drii(a, b);