JosephLand CodeChef Solution

Problem -JosephLand CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

<<Previous CodeChef Problem Next Codechef Problem>>

JosephLand CodeChef Solution in C++14

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

#ifdef LOCAL
#include "H:\code\codeforces\debug.h"
#else
#define debug(...)
#define sdebug(...)
#endif

const int N = (int) 1e5 + 5;

vector<int> adj[N]; //node, edge, cost
vector<pair<LL, LL > > info[N];
vector<LL> curDis;
LL ans[N];

struct ST {
  LL tree[4 * N];
  static const LL inf = LLONG_MAX;
  ST() {
   memset(tree, 0, sizeof tree);
  }
  void update(int node, int b, int e, int i, LL x) {
    if (b > i || e < i) return;
    if (b == e && b == i) {
      tree[node] = x; // update
      return;
    }
    int mid = (b + e) >> 1, l = node << 1, r = l | 1;
    update(l, b, mid, i, x);
    update(r, mid + 1, e, i, x);
    tree[node] = min(tree[l], tree[r]); // change this
  }
  LL query(int node, int b, int e, int i, int j) {
    if (b > j || e < i) return inf; // return appropriate value
    if (b >= i && e <= j) return tree[node];
    int mid = (b + e) >> 1, l = node << 1, r = l | 1;
    return min(query(l, b, mid, i, j), query(r, mid + 1, e, i, j)); // change this
  }
}t;

void dfs(int node, int par) {
	if (node == 1) {curDis.push_back(0), t.update(1, 1, N, (int) curDis.size(), ans[node]);}
	else {
		ans[node] = LLONG_MAX;
		for (auto u : info[node]) {
			LL cost = u.second, edge = u.first;
			LL go = t.query(1, 1, N, max((LL)curDis.size() - edge + 1, 0LL), (int) curDis.size());
			ans[node] = min(go + cost, ans[node]);
		}                     
		curDis.push_back(ans[node]);
		t.update(1, 1, N, (int) curDis.size(), ans[node]);
	}
	for (int u : adj[node]) {
		if (u != par) dfs(u, node);
	} 
	curDis.pop_back();
}

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 1; i < N; ++i) ans[i] = LLONG_MAX;
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	ans[1] = 0;
	for (int i = 1; i <= m; ++i) {
		LL u, c, w; cin >> u >> w >> c;
		info[u].push_back({w, c}); //edge, cost
	}
	dfs(1, -1);
	int q; cin >> q;
	while (q--) {
		int node; cin >> node;
		cout << ans[node] << "\n";
	}
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1; 
   // cin >> t;
    while(t--) solve();
}

JosephLand CodeChef Solution in C

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

#define NMAX 100000
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;

typedef struct _Ticket {
    int dist;
    int cost;
} Ticket;

typedef struct _CostSlab {
    int start_dist, end_dist;
    int cost;
} CostSlab;

typedef struct _City {
    #define ALLOC_CHUNK_COUNT 1000
    int *arrival_city_ids;
    int arrival_id_count, arrival_alloc_count;
    Ticket *tickets;
    int num_tickets, ticket_alloc_count;
    CostSlab *cost_slabs;
    int num_cslabs, cslab_alloc_count;
    int max_dist; // max distance that can be reached from here using any ticket
    ll min_cost; // min cost to capital
} City;

City cities[NMAX] = {0};
int path_city_ids[NMAX];
ll path_min_costs[NMAX];

int Ticket_cmp(const void *p1, const void *p2)
{
    Ticket *t1, *t2;
    t1 = (Ticket *)p1;
    t2 = (Ticket *)p2;
    if (t1->cost != t2->cost)
        return t1->cost - t2->cost;
    return t2->dist - t1->dist; // for same cost, more distance is better
}

#define MAX_PO2 32 
int po2_max; // actual
ll *min_arr[MAX_PO2 + 1];
ll *min_arr_chunk_data[MAX_PO2 + 1];

ll get_min_cost(ll *arr, int L, int R)
{
    int chunk_size = R - L + 1;
    if (chunk_size == 1)
        return arr[L];
    if (chunk_size == 2)
        return min(arr[L], arr[R]);
    int po2;
    for (po2 = po2_max; (1 << po2) > chunk_size; )
        po2--;
    int po2_sz = (1 << po2);
    int div = L / po2_sz;
    if (L % po2_sz)
        div++;
    ll min_val = -1, min_part1 = -1;
    int br1 = div * po2_sz;
    if (br1 + po2_sz - 1 > R) {
        // po2 chunk not contained
        po2--;
        po2_sz = (1 << po2);
        div = L / po2_sz;
        if (L % po2_sz)
            div++;
        br1 = div * po2_sz;
    }
    if (br1 > L)
        min_val = min_part1 = get_min_cost(arr, L, br1 - 1);
    ll min_part2 = min_arr[po2][div];
    if (min_val == -1 || min_part2 < min_val)
        min_val = min_part2;
    int br2 = br1 + po2_sz;
    ll min_part3 = -1;
    if (br2 <= R) {
        min_part3 = get_min_cost(arr, br2, R);
        if (min_val == -1 || min_part3 < min_val)
            min_val = min_part3;
    }
    return min_val;
}

void traverse_cities(int id, int N, int dist_from_capital, int *path_city_ids, ll *path_min_costs)
{
    static int min_arr_initialized = 0;
    int po2, chunk_sz, num_chunks;
    if (!min_arr_initialized) {
        for (po2 = 1; po2 <= MAX_PO2; po2++) {
            chunk_sz = (1 << po2);
            if (chunk_sz > N)
                break;
            po2_max = po2;
            num_chunks = N / chunk_sz + ((N % chunk_sz) ? 1 : 0);
            min_arr[po2] = (ll *)malloc(num_chunks * sizeof(ll));
            min_arr_chunk_data[po2] = (ll *)malloc(num_chunks * chunk_sz * sizeof(ll));
        }
        min_arr_initialized = 1;
    }
    City *cp = &cities[id];
    int i;
    if (id == 0)
        cp->min_cost = 0;
    else {
        ll min_cost = -1;
        int prev_sz = 0;
        for (i = 0; i < cp->num_cslabs; i++) {
            CostSlab *cslabp = &cp->cost_slabs[i];
            int slab_dist = cslabp->end_dist - cslabp->start_dist + 1;
            int path_start_i = dist_from_capital - slab_dist - prev_sz;
            if (path_start_i < 0)
                path_start_i = 0;
            int seg_count = min(dist_from_capital, slab_dist);
            int path_end_i = path_start_i + seg_count - 1;
            ll this_cost = get_min_cost(path_min_costs, path_start_i, path_end_i) + (ll)cslabp->cost;
            if (min_cost == -1 || this_cost < min_cost)
                min_cost = this_cost;
            prev_sz = seg_count;
            if (path_start_i == 0)
                break;
        }
        cp->min_cost = min_cost;
    }
    path_city_ids[dist_from_capital] = id;
    path_min_costs[dist_from_capital] = cp->min_cost;
    for (po2 = 1; po2 <= po2_max; po2++) {
        chunk_sz = (1 << po2);
        int chunk_i = dist_from_capital / chunk_sz;
        int i_in_chunk = dist_from_capital % chunk_sz;
        if (i_in_chunk == 0) {
            min_arr[po2][chunk_i] = min_arr_chunk_data[po2][chunk_i * chunk_sz] = cp->min_cost;
        } else {
            int ind_chunk_data = chunk_i * chunk_sz + i_in_chunk;
            min_arr[po2][chunk_i] = min_arr_chunk_data[po2][ind_chunk_data] = min(min_arr_chunk_data[po2][ind_chunk_data - 1], cp->min_cost); 
        }
    }
    for (i = 0; i < cp->arrival_id_count; i++)
        traverse_cities(cp->arrival_city_ids[i], N, dist_from_capital + 1, path_city_ids, path_min_costs);
}

int main()
{
    int N, M, i, j;
    scanf("%d %d", &N, &M);
    for (i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        cities[b - 1].arrival_id_count++;
        if (cities[b - 1].arrival_id_count > cities[b - 1].arrival_alloc_count) {
            cities[b - 1].arrival_alloc_count += ALLOC_CHUNK_COUNT;
            if (!cities[b - 1].arrival_city_ids) 
                cities[b - 1].arrival_city_ids = (int *)malloc(cities[b - 1].arrival_alloc_count * sizeof(int));
            else
                cities[b - 1].arrival_city_ids = (int *)realloc(cities[b - 1].arrival_city_ids,
                                                    cities[b - 1].arrival_alloc_count * sizeof(int));
        }
        cities[b - 1].arrival_city_ids[cities[b - 1].arrival_id_count - 1] = a - 1;
    }
    for (i = 0; i < M; i++) {
        int v, k, w;
        scanf("%d %d %d", &v, &k, &w);
        City *cp = &cities[v - 1];
        cp->num_tickets++;
        if (cp->num_tickets > cp->ticket_alloc_count) {
            cp->ticket_alloc_count += ALLOC_CHUNK_COUNT;
            if (!cp->tickets)
                cp->tickets = (Ticket *)malloc(cp->ticket_alloc_count * sizeof(Ticket));
            else
                cp->tickets = (Ticket *)realloc(cp->tickets, cp->ticket_alloc_count * sizeof(Ticket));
        }
        Ticket *tp = cp->tickets + cp->num_tickets - 1;
        tp->dist = k;
        tp->cost = w;
    }
    // process tickets info
    for (i = 0; i < N; i++) {
        City *cp = &cities[i];
        qsort(cp->tickets, cp->num_tickets, sizeof(Ticket), Ticket_cmp);
        int max_dist = 0;
        for (j = 0; j < cp->num_tickets; j++) {
            Ticket *tp = &cp->tickets[j];
            if (tp->dist <= max_dist)
                continue;
            cp->num_cslabs++;
            if (cp->num_cslabs > cp->cslab_alloc_count) {
                cp->cslab_alloc_count += ALLOC_CHUNK_COUNT;
                if (!cp->cost_slabs)
                    cp->cost_slabs = (CostSlab *)malloc(cp->cslab_alloc_count * sizeof(CostSlab));
                else
                    cp->cost_slabs = (CostSlab *)realloc(cp->cost_slabs, cp->cslab_alloc_count * sizeof(CostSlab));
            }
            CostSlab *cslabp = cp->cost_slabs + cp->num_cslabs - 1;
            cslabp->start_dist = max_dist + 1;
            cslabp->end_dist = max_dist = tp->dist;
            cslabp->cost = tp->cost;
        }
        cp->max_dist = max_dist;
    }
    // traverse cities
    traverse_cities(0, N, 0, path_city_ids, path_min_costs);

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int h;
        scanf("%d", &h);
        printf("%lld\n", cities[h - 1].min_cost);
    }

    return 0;
}

JosephLand CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    
	static LinkedList<Integer>adj[];
	static LinkedList<int[]> tickets[];

	public static void main(String[] args) {
		
		try {
				BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
				String s[]=br.readLine().split(" ");
				int n=Integer.parseInt(s[0]);
				int m=Integer.parseInt(s[1]);
				
				adj=new LinkedList[n];
				for(int i=0;i<n;i++)	adj[i]=new LinkedList<>();
				
				for(int i=0;i<n-1;i++) {
					s=br.readLine().split(" ");
					int p=Integer.parseInt(s[0])-1;
					int q=Integer.parseInt(s[1])-1;
					
					adj[q].add(p);
				}
				
				tickets=new LinkedList[n];
				for(int i=0;i<n;i++)	tickets[i]=new LinkedList<>();
				
				for(int i=0;i<m;i++) {
					s=br.readLine().split(" ");
					int p=Integer.parseInt(s[0])-1;
					int q=Integer.parseInt(s[1]);
					int r=Integer.parseInt(s[2]);
					
					int ar[]= {q,r};
					tickets[p].add(ar);
				}
				
				long a[]=new long[n];
				long tree[]=new long[4*n+1];
				Arrays.fill(a, Long.MAX_VALUE);
				Arrays.fill(tree, Long.MAX_VALUE);
				
				dfs(tree,0,a,0);
				
				int q=Integer.parseInt(br.readLine());
				StringBuilder sb=new StringBuilder();
				while(q-->0) {
					int p=Integer.parseInt(br.readLine())-1;
					sb.append(a[p]+"\n");
				}
				System.out.println(sb);
		}
		catch(Exception e) {
			return;
		}

	}
	
	static void dfs(long tree[],int pos,long a[],int cur) {
		
		int n=a.length;
		long min=Long.MAX_VALUE;
		
		for(int[] i:tickets[cur]) {
			long tempMin=i[1];
			int l=pos-i[0]<0?0:pos-i[0];
			int r=pos-1;
			
			tempMin+=query(tree,1,0,n-1,l,r);
			
			min=Long.min(min, tempMin);
		}
		
		update(tree,1,0,n-1,pos,pos==0?0:min);
		a[cur]=min;
		if(pos==0)	a[cur]=0;
		
		for(int i:adj[cur]) {
			dfs(tree,pos+1,a,i);
		}
		update(tree,1,0,n-1,pos,Long.MAX_VALUE);
	}
	
	static long query(long tree[],int i,int s,int e,int qs,int qe) {
		
		if(qs>e || qe<s) {
			return Long.MAX_VALUE;
		}
		
		if(qs<=s && qe>=e) {
			return tree[i];
		}
		
		int mid=s+e>>1;
		return Long.min(query(tree,2*i,s,mid,qs,qe), query(tree,2*i+1,mid+1,e,qs,qe));
	}
	
	static void update(long tree[],int ind,int s,int e,int i,long val) {
		
		if(i<s || i>e) {
			return;
		}
		
		if(s==e) {
			tree[ind]=val;
			return;
		}
		
		int mid=s+e>>1;
		update(tree,2*ind,s,mid,i,val);
		update(tree,2*ind+1,mid+1,e,i,val);
		tree[ind]=Long.min(tree[2*ind], tree[2*ind+1]);
		return;
	}

}

JosephLand CodeChef Solution in PYTH

import sys		
from math import log,ceil
sys.setrecursionlimit(1000005)
inf=pow(10,18)
def update(idx,low,high,pos,val):
    if idx<low or idx>high:
        return
    if low==high:
        st[pos]=val
        return
    mid=(low+high)>>1
    if idx<=mid:
        update(idx,low,mid,2*pos+1,val)
    else:
        update(idx,mid+1,high,2*pos+2,val)
    st[pos] = min(st[2 * pos + 1], st[2 * pos + 2])
 
def query(qlow, qhigh, low, high, pos):
    if qlow <= low and qhigh >= high: #TOTAL OVERLAP
        return st[pos]
    if qlow > high or qhigh < low: #NO OVERLAP
        return inf
    mid = (low + high)>>1
    #PARTIAL OVERLAP
    left=query(qlow, qhigh, low, mid, 2 * pos + 1)
    right=query(qlow, qhigh, mid+1, high, 2 * pos + 2)
    return min(left,right)
 
def dfs(cur_node,depth):
    if cur_node!=0:
        for k,w in tickets[cur_node]:
            dp[cur_node]=min(dp[cur_node],query(max(0,depth-k),depth,0,n-1,0)+w)
    update(depth,0,n-1,0,dp[cur_node])
    for v in tree[cur_node]:
        dfs(v,depth+1)
    update(depth,0,n-1,0,inf)
 
author="tanmoy khatua"
aa,bb=0,0
n,m=map(int,raw_input().split())
tree=[[] for i in xrange(n)]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    tree[b-1].append(a-1)
tickets=[[] for i in xrange(n)]
for i in xrange(m):
    v,k,w=map(int,raw_input().split())
    tickets[v-1].append((k,w))
dp=[inf for i in xrange(n)]
dp[0]=0
st=[inf for i in xrange(5*n)]
update(0,0,n-1,0,0)
dfs(0,0)
q=input()
for i in xrange(q):
    print dp[input()-1]

JosephLand CodeChef Solution in C#

using Boilerplate.IO;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

public class Solver
{
    private readonly StreamReader reader;
    private readonly StreamWriter writer;

    public Solver(StreamReader reader, StreamWriter writer)
    {
        this.reader = reader;
        this.writer = writer;
    }

    public void Generate()
    { }

    public void RmqUpdate(long[][] store, int level, int pos, long val)
    {
        store[0][pos] = val;
        for (int i = 1; i < level; ++i)
        {
            pos >>= 1;
            store[i][pos] = store[i - 1][pos << 1];
            if ((pos << 1) + 1 < store[i - 1].Length)
                store[i][pos] = Math.Min(store[i][pos], store[i - 1][(pos << 1) + 1]);
        }
    }

    public long RmqGet(long[][] store, int level, int l, int r)
    {
        long res = long.MaxValue;
        for (int i = 0; i < level && l <= r; ++i)
        {
            if ((l & 1) == 1)
                res = Math.Min(res, store[i][l]);
            l = (l + 1) >> 1;
            if ((r & 1) == 0)
                res = Math.Min(res, store[i][r]);
            r = (r - 1) >> 1;
        }
        return res;
    }

    int[] child;
    int[] next;
    long[] cost;
    Dictionary<int, List<Tuple<int, int>>> tcts;

    int DEPTH = 17;
    long[][] stack;    

    public void Dfs(int node, int level)
    {        
        if (level > 0 && tcts.ContainsKey(node))
        {
            var best = long.MaxValue;
            foreach (var tpl in tcts[node])
            {
                var val = RmqGet(stack, DEPTH, Math.Max(0, level - tpl.Item1), level - 1);
                best = Math.Min(best, val + tpl.Item2);
            }
            RmqUpdate(stack, DEPTH, level, cost[node] = best);
        }
        else
            cost[node] = 0;
        var chld = child[node];
        while (chld != -1)
        {
            Dfs(chld, level + 1);
            chld = next[chld];
        }
    }

    public void Do()
    {
        var n = reader.ReadInt();
        var m = reader.ReadInt();
        child = new int[n];
        next = new int[n];
        cost = new long[n];
        tcts = new Dictionary<int, List<Tuple<int, int>>>();
        stack = new long[DEPTH][];
        for (int i = 0; i < DEPTH; ++i)
        {
            stack[i] = new long[n + 1];
        }
        RmqUpdate(stack, DEPTH, n, long.MaxValue);
        for (int i = 0; i < n; ++i)
            child[i] = -1;
        for (int i = 0; i < n - 1; ++i)
        {
            var a = reader.ReadInt() - 1;
            var b = reader.ReadInt() - 1;
            next[a] = child[b];
            child[b] = a;
        }        
        for (int i = 0;i < m; ++i)
        {
            var v = reader.ReadInt() - 1;
            var k = reader.ReadInt();
            var w = reader.ReadInt();
            if (!tcts.ContainsKey(v))
                tcts[v] = new List<Tuple<int, int>>();
            tcts[v].Add(Tuple.Create(k, w));
        }        
        Dfs(0, 0);
        var q = reader.ReadInt();
        while (q-- > 0)
        {
            var fr = reader.ReadInt() - 1;
            writer.WriteLine(cost[fr]);
        }
    }
}

#region launch
class Program
{
    static void Main(string[] args)
    {
        using (var writer = new FormattedStreamWriter(
#if SOLVER_RUN_LOCAL
"output.txt"
#else 
         Console.OpenStandardOutput()
#endif
))
        {
            using (var reader = new StreamReader(
#if SOLVER_RUN_LOCAL
"input.txt"
#else 
         Console.OpenStandardInput() 
#endif
))
            {
#if SOLVER_RUN_LOCAL
                var stopw = new Stopwatch();
                stopw.Start();
#endif
                new Solver(reader, writer).Do();
#if SOLVER_RUN_LOCAL
                stopw.Stop();
                writer.WriteLine("> {0}ms", stopw.ElapsedMilliseconds);
#endif
            }
        }
    }
}
#endregion

namespace Boilerplate.IO
{
    #region helpers
    class FormattedStreamWriter : StreamWriter
    {
        public FormattedStreamWriter(Stream stream) : base(stream) { }
        public FormattedStreamWriter(string filePath) : base(filePath) { }
        public override IFormatProvider FormatProvider
        {
            get
            {
                return CultureInfo.InvariantCulture;
            }
        }
    }
    static class IOExtensions
    {
        public static string ReadString(this StreamReader reader)
        {
            return reader.ReadToken();
        }
        public static int ReadInt(this StreamReader reader)
        {
            return int.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
        }
        public static long ReadLong(this StreamReader reader)
        {
            return long.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
        }
        public static double ReadDouble(this StreamReader reader)
        {
            return double.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
        }
        public static decimal ReadDecimal(this StreamReader reader)
        {
            return decimal.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
        }

        static Queue<string> buffer = new Queue<string>(100);
        static string ReadToken(this StreamReader reader)
        {
            while (buffer.Count == 0)
            {
                reader.ReadLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).ToList().ForEach((t) =>
                {
                    buffer.Enqueue(t);
                });
            } return buffer.Dequeue();
        }
    }
    #endregion
}

JosephLand CodeChef Solution in GO

package main
import ("fmt"; "bufio"; "os")

const (
	MAXN = 100000
	INF = int64(1e17)
)

//----------------------------------------------------------
type City struct {
	parent int
	costToRoot int64
	children []int
	tickets []Ticket
}

type Ticket struct {
	cost int
	uses int
}

var cities []City

func initCities(N int) {
	cities = make([]City, N)
	for i:=0; i<N; i++ {
		cities[i].children = make([]int, 0, 2)
		cities[i].tickets = make([]Ticket, 1)
	}
}


func maxLevel(idx int) int {
	maxlvl := 0
	for _, ch := range cities[idx].children {
		maxlvl = max(maxlvl, maxLevel(ch))
	}
	return 1+maxlvl
}

//----------------------------------------------------------
type Interval struct {
	l, r int
}

func (this Interval) disjoint(other Interval) bool {
	return this.r<other.l || this.l>other.r
}

func (this Interval) insideOf(other Interval) bool {
	return this.l>=other.l && this.r<=other.r
}

func (this Interval) contains(pos int) bool {
	return this.l <= pos && pos <= this.r
}

var tree []int64

func childrenIndex(nodeIdx int, ivlTree Interval) (lchild, rchild, mid int) {
	lchild = 2*nodeIdx+1 
	rchild = 2*nodeIdx+2
	mid = (ivlTree.l + ivlTree.r)/2
	return
}

func initSegmentTree(size int) {
	tree = make([]int64, 4*size)
}


func query(nodeIdx int, ivlTree, ivlQuery Interval) int64 {
	if(ivlTree.disjoint(ivlQuery)) {
		return INF
	}

	if ivlTree.insideOf(ivlQuery) {
		return tree[nodeIdx]
	}

	var lchild, rchild, mid = childrenIndex(nodeIdx, ivlTree)
	var lv = query(lchild, Interval{ivlTree.l,   mid}, ivlQuery)
	var rv = query(rchild, Interval{mid+1, ivlTree.r}, ivlQuery)
	return min(lv, rv)
}

func update(nodeIdx int, ivlTree Interval, pos int, newval int64) {
	if !ivlTree.contains(pos) {
		return
	}

	if ivlTree.l==ivlTree.r {
		if ivlTree.l != pos {
			panic("Wrong navigation")
		}
		tree[nodeIdx] = newval
		return
	}

	var lchild, rchild, mid = childrenIndex(nodeIdx, ivlTree)
	update(lchild, Interval{ivlTree.l,   mid}, pos, newval)
	update(rchild, Interval{mid+1, ivlTree.r}, pos, newval)
	tree[nodeIdx] = min(tree[lchild], tree[rchild])
}

func querySegment(l, r int) int64 {
	return query(0, Interval{0, len(cities)-1}, Interval{l, r});
}

func solveCity(cityIdx, level int) {
	best := INF
	if cityIdx == 0 {
		best = 0
	} else {
		for _, ticket := range cities[cityIdx].tickets {
			best = min(best, int64(ticket.cost)+querySegment(level-ticket.uses, level-1))
		}
	}
	//println(best)
	cities[cityIdx].costToRoot = best
	update(0, Interval{0, len(cities)-1}, level, best)

	for _, ch := range cities[cityIdx].children {
		solveCity(ch, level+1)
	}
}


func main() {
	scanner = bufio.NewScanner(bufio.NewReader(os.Stdin))
	scanner.Split(bufio.ScanWords)
	var out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	
	N, M := readNum(), readNum()

	initCities(N)

	for i:=0; i<N-1; i++ {
		a, b := readNum()-1, readNum()-1
		cities[a].parent = b
		cities[b].children = append(cities[b].children, a)
	}

	for i:=0; i<M; i++ {
		v, k, w := readNum()-1, readNum(), readNum()
		cities[v].tickets = append(cities[v].tickets, Ticket{w, k})
	}

	initSegmentTree(maxLevel(0)+1)
	solveCity(0, 0)

	
	//fmt.Fprintf(out, "%v", mindist);

	for i:=readNum(); i>0; i-- {
		h := readNum()-1
		fmt.Fprintln(out, cities[h].costToRoot)
	}
}


//--------------------------------------------------------------
var scanner *bufio.Scanner

func readBytes() []byte {
	if !scanner.Scan() {
		panic(fmt.Sprintf("Error scanning: %v", scanner.Err()))
	}
	return scanner.Bytes()
}

func readNum() int {
	var bs = readBytes()
	var num = 0
	for i:=0; i<len(bs); i++ {
		digit := bs[i]
		if digit<'0' || digit>'9' {
			panic(fmt.Sprintf("Not a digit: %c", digit))
		}
		num = num*10 + int(digit-'0')
	}
	return num
}


func min(a, b int64) int64 {
	if a<b {
		return a
	} else {
		return b
	}
}

func max(a, b int) int {
	if a>b {
		return a
	} else {
		return b
	}
}

JosephLand CodeChef Solution Review:

In our experience, we suggest you solve this JosephLand CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the JosephLand CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this JosephLand CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn