All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Diverging Directions
Tag(s):

Medium

Problem
Editorial
Analytics

You are given a directed weighted graph with n nodes and \(2n-2\) edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to \(2n-2\). The graph's edges can be split into two parts.

  • The first \(n-1\) edges will form a rooted spanning tree, with node 1 as the root. All these edges will point away from the root.
  • The last \(n-1\) edges will be from node i to node 1, for all \(2 \leq i \leq n\).

You are given q queries. There are two types of queries

  • \(1 i w\): Change the weight of the i-th edge to w
  • \(2 u v\): Print the length of the shortest path from node u to v

Given these queries, print the shortest path lengths.

Input Format

The first line of input will contain two integers \(n,q\), the number of nodes, and the number of queries, respectively.

The next \(2n-2\) integers will contain 3 integers \(a_i, b_i, c_i\), denoting a directed edge from node \(a_i\) to node \(b_i\) with weight \(c_i\).

The first \(n-1\) of these lines will describe a rooted spanning tree pointing away from node 1, while the last \(n-1\) of these lines will have \(b_i = 1\).

The next q lines will contain 3 integers, describing a query in the format described in the statement.

Output Format

For each type 2 query, print the length of the shortest path in its own line.

Constraints

\(2 \leq n \leq 200\,000\)

\(1 \leq q \leq 200\,000\)

\(1 \leq a_i, b_i \leq n\)

All edge weights will be between 1 and \(10^6\).

The edges \((a_1,b_1), (a_2,b_2), \ldots (a_{n-1},b_{n-1})\) will describe a rooted spanning tree pointing away from node 1.

\(b_j = 1\) for \(n \leq j \leq 2n-2\).

\(a_n, a_{n+1}, \ldots, a_{2n-2}\) will be distinct and between 2 and n.

SAMPLE INPUT
5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4
SAMPLE OUTPUT
0
1
4
8
100
132
10
Explanation

.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

IndiaHacks 2017: Programming [Wave 2.0- Eliminator]

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?