# Self-Driving Bus

### Problem Statement :

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:

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

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 x 10^5
1  <=  ai , bi  <=  n

Output Format

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

### Solution :

Solution in C :

In  C++  :

#include<iostream>
#include<vector>
using namespace std;

typedef long long int lli;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
typedef vector<vi> vii;

const lli MAXN = 200200;
lli par[MAXN], upr[MAXN],dnr[MAXN];
lli run_upr[MAXN], run_dnr[MAXN], grand[MAXN];
vii G(MAXN);

void set_parents(lli m,lli a,lli b, lli p){
upr[m] = max(m,upr[p]);
dnr[m] = min(m,dnr[p]);
par[m] = p;
grand[m] = grand[p];
for(auto it = G[m].begin() ; it != G[m].end(); it++){
if((*it) < a || (*it) >= b || (*it) == p) continue;
set_parents(*it, a, b, m);
}
}

lli middle_case(lli m, lli a, lli b){
run_upr[m] = run_dnr[m] = m;
lli aux;
for(aux = m ; aux < b && grand[aux] == m ; aux++);
b = aux;
for(aux = m ; aux >= a && grand[aux] == m ; aux--);
a = aux + 1;

for(lli i = m + 1 ; i < b ; i++){
run_upr[i] = max(run_upr[i-1], upr[i]);
run_dnr[i] = min(run_dnr[i-1], dnr[i]);
}

for(lli i = m - 1 ; i >= a ; i--){
run_upr[i] = max(run_upr[i+1], upr[i]);
run_dnr[i] = min(run_dnr[i+1], dnr[i]);
}
lli total = 0; // {m}
// Contamos [i,d] con i <= m/2, d>= m/2
for(lli d = m, l = m + 1, r = m+ 1, ct = 0; d < b ; d++){
if(d != run_upr[d]) continue;
for(; l - 1>= a && d >= run_upr[l- 1] ;l--){
if(l-1 == run_dnr[l-1]) ct++;
}
for(; r - 1> run_dnr[d] && r > l; r--){
if(r - 1 == run_dnr[r-1]) ct--;
}
total += ct;
}
}

lli solve(lli a, lli b){
if(a == b){
return 0;
}
if(a + 1 == b){
return 1;
}
lli m = (a+b)/2;
lli x,y,z;
upr[m] = par[m] = dnr[m] = grand[m] = m;
set_parents(m,a,b,m);
x = middle_case(m,a,b);
y = solve(a,m);
z = solve(m + 1,b);
return (x+y+z);
}

int main(){
lli n, a,b;
cin >> n;
for(int i = 1 ; i<n;i++){
cin >> a >> b;
a--;
b--;
G[a].push_back(b);
G[b].push_back(a);
}
cout << solve(0,n) << endl;
return 0;
}

In   Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int nodeNum = Integer.parseInt(sc.nextLine());
List<List<Integer>> refer = new ArrayList<List<Integer>>();
for(int i=0; i<nodeNum; i++) {
}

while(sc.hasNextLine()) {
String[] pair = sc.nextLine().split(" ");
putRefer(refer, pair[0], pair[1]);
}

int result = 0;
for(int i=1; i<=nodeNum; i++) {
boolean[] battleFront = new boolean[nodeNum];
expandFront(i, battleFront, refer);
result++;
int upto = i;
for(int j=i+1; j<=nodeNum; j++) {
if(battleFront[j-1]) {
expandFront(j, battleFront, refer);
if(allInFront(battleFront, upto, j)) {
result++;
for(int k=upto+1; k<j; k++) {
expandFront(k, battleFront, refer);
}
upto = j;
}
}
}
}

System.out.println(result);
}

public static void putRefer(List<List<Integer>> refer, String s1, String s2) {
int a = Integer.parseInt(s1);
int b = Integer.parseInt(s2);
List<Integer> tmp = refer.get(a-1);
tmp = refer.get(b-1);
}

public static void expandFront(int i,
boolean[] battleFront, List<List<Integer>> refer) {
List<Integer> tmp = refer.get(i-1);
battleFront[i-1] = true;
if(tmp == null) {
return;
}
for(Integer thisInt : tmp) {
battleFront[thisInt-1] = true;
}
}

public static boolean allInFront(boolean[] battleFront, int upto, int j) {
for(int i=upto; i<j-1; i++) {
if(battleFront[i] == false) {
return false;
}
}
return true;
}

public static void printArray(boolean[] battleFront) {
for(boolean b : battleFront) {
System.out.print(b + " ");
}
System.out.println(" ");
}

public static void printList(List<List<Integer>> refer) {
for(List<Integer> l : refer) {
if(l == null) {
System.out.println("null ");
}
else {
for(Integer ii : l) {
System.out.print(ii + " ");
}
System.out.println(" ");
}
}
}
}

In   Python3 :

from heapq import *
n=int(input())
neighbors = {}

for x in range(n):
neighbors[x] = []
for i in range(n-1):
a, b = map(int,input().split())
neighbors[a-1].append(b-1)
neighbors[b-1].append(a-1)
def search(source):
ans = 0
cur_max = 0
cur_len = 0
heap = [source]
vis = [False for i in range(n)]
while len(heap) > 0:
x = heappop(heap)
cur_max = max(cur_max, x)
cur_len += 1
vis[x] = True
if cur_max - source + 1 == cur_len:
ans += 1
for y in neighbors[x]:
if y >= source and vis[y] == False:
heappush(heap, y)
return ans
ans = 0
prev = 0
for x in range(n-1, -1, -1):
neigh = 0
plus = 0
for y in neighbors[x]:
if y > x:
neigh += 1
if y == x + 1:
plus = 1
if plus == neigh and plus == 1:
prev += 1
else:
prev = search(x)
ans += prev
print(ans)

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element