Distance Queries on a Tree

AtCoder

IDabc294_g

Time4000ms

Memory256MB

Difficulty—

You are given a tree $T$ with $N$ vertices. Edge $i$ $(1\leq i\leq N-1)$ connects vertices $u _ i$ and $v _ i$, and has a weight of $w _ i$. Process $Q$ queries in order. There are two kinds of queries as follows. * `1 i w` : Change the weight of edge $i$ to $w$. * `2 u v`：Print the distance between vertex $u$ and vertex $v$. Here, the distance between two vertices $u$ and $v$ of a tree is the smallest total weight of edges in a path whose endpoints are $u$ and $v$. ## Constraints * $1\leq N\leq 2\times10^5$ * $1\leq u _ i,v _ i\leq N\ (1\leq i\leq N-1)$ * $1\leq w _ i\leq 10^9\ (1\leq i\leq N-1)$ * The given graph is a tree. * $1\leq Q\leq 2\times10^5$ * For each query of the first kind, * $1\leq i\leq N-1$, and * $1\leq w\leq 10^9$. * For each query of the second kind, * $1\leq u,v\leq N$. * There is at least one query of the second kind. * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $u _ 1$ $v _ 1$ $w _ 1$ $u _ 2$ $v _ 2$ $w _ 2$ $\vdots$ $u _ {N-1}$ $v _ {N-1}$ $w _ {N-1}$ $Q$ $\operatorname{query} _ 1$ $\operatorname{query} _ 2$ $\vdots$ $\operatorname{query} _ Q$ Here, $\operatorname{query} _ i$ denotes the $i$\-th query and is in one of the following format: $1$ $i$ $w$ $2$ $u$ $v$ [samples]

Samples

Input #1

Output #1

9
19
11

The initial tree is shown in the figure below.
![image](https://img.atcoder.jp/abc294/b11e5bebc4d34f82fc3cd43899df453b.png)
Each query should be processed as follows.

*   The first query asks you to print the distance between vertex $2$ and vertex $3$. Edge $1$ and edge $2$, in this order, form a path between them with a total weight of $9$, which is the minimum, so you should print $9$.
*   The second query asks you to print the distance between vertex $1$ and vertex $5$. Edge $3$ and edge $4$, in this order, form a path between them with a total weight of $19$, which is the minimum, so you should print $19$.
*   The third query changes the weight of edge $3$ to $1$.
*   The fourth query asks you to print the distance between vertex $1$ and vertex $5$. Edge $3$ and edge $4$, in this order, form a path between them with a total weight of $11$, which is the minimum, so you should print $11$.

Input #2

7
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
3
2 1 6
1 1 294967296
2 1 6

Output #2

5000000000
4294967296

Note that the answers may not fit into $32$\-bit integers.

Input #3

1
1
2 1 1

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Distance Queries on a Tree",
    "description": {
      "content": "You are given a tree $T$ with $N$ vertices. Edge $i$ $(1\\leq i\\leq N-1)$ connects vertices $u _ i$ and $v _ i$, and has a weight of $w _ i$. Process $Q$ queries in order. There are two kinds of querie",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc294_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree $T$ with $N$ vertices. Edge $i$ $(1\\leq i\\leq N-1)$ connects vertices $u _ i$ and $v _ i$, and has a weight of $w _ i$.\nProcess $Q$ queries in order. There are two kinds of querie...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments