102946: [Atcoder]ABC294 G - Distance Queries on a Tree
Description
Score : $600$ points
Problem Statement
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$
Output
Print $q$ lines, where $q$ is the number of queries of the second kind. The $j$-th line $(1\leq j\leq q)$ should contain the answer to the $j$-th query of the second kind.
Sample Input 1
5 1 2 3 1 3 6 1 4 9 4 5 10 4 2 2 3 2 1 5 1 3 1 2 1 5
Sample Output 1
9 19 11
The initial tree is shown in the figure below.
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$.
Sample 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
Sample Output 2
5000000000 4294967296
Note that the answers may not fit into $32$-bit integers.
Sample Input 3
1 1 2 1 1
Sample Output 3
0
Sample Input 4
8 1 2 105 1 3 103 2 4 105 2 5 100 5 6 101 3 7 106 3 8 100 18 2 2 8 2 3 6 1 4 108 2 3 4 2 3 5 2 5 5 2 3 1 2 4 3 1 1 107 2 3 1 2 7 6 2 3 8 2 1 5 2 7 6 2 4 7 2 1 7 2 5 3 2 8 6
Sample Output 4
308 409 313 316 0 103 313 103 525 100 215 525 421 209 318 519
Input
题意翻译
给定一颗有 $n$ 个节点的树,带边权,要进行 $Q$ 次操作,操作有两种: `1 i w`:将第 $i$ 条边的边权改为 $w$。 `2 u v`:询问 $u,v$ 两点的距离。 ### 输入格式 第一行,一个正整数 $n$。 接下来 $n-1$ 行,每行三个数 $u,v,w$,表示一条树边。 接下来一个正整数 $Q$。 接下来 $Q$ 行,每行三个数,描述一个询问,格式如上。 ### 输出格式 对于每个 $2$ 操作,输出一行一个数,表示该询问的答案。 ### 说明/提示 $1\le n,Q\le 2\times10^5,1\le w_i\le 10^9$Output
分数:$600$分
问题描述
你被给定一棵有$N$个顶点的树。 边$i$ $(1\leq i\leq N-1)$连接顶点$u _ i$和顶点$v _ i$,其权重为$w _ i$。
按顺序处理$Q$个查询。有两种类型的查询如下。
1 i w
: 将边$i$的权重改为$w$。2 u v
:打印顶点$u$和顶点$v$之间的距离。
其中,树中两个顶点$u$和$v$之间的距离是连接它们的路径中边的权重总和的最小值。
约束条件
- $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)$
- 给定的图是一棵树。
- $1\leq Q\leq 2\times10^5$
- 对于第一种类型的查询中的每个查询,
- $1\leq i\leq N-1$,并且
- $1\leq w\leq 10^9$。
- 对于第二种类型的查询中的每个查询,
- $1\leq u,v\leq N$。
- 至少有一个第二种类型的查询。
- 输入中的所有值都是整数。
输入
输入从标准输入按以下格式给出:
$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$
其中,$\operatorname{query} _ i$表示第$i$个查询,可以是以下格式之一:
$1$ $i$ $w$
$2$ $u$ $v$
输出
打印$q$行,其中$q$是第二种类型的查询的数量。 第$j$行 $(1\leq j\leq q)$ 应包含第二种类型的第$j$个查询的答案。
样例输入 1
5 1 2 3 1 3 6 1 4 9 4 5 10 4 2 2 3 2 1 5 1 3 1 2 1 5
样例输出 1
9 19 11
初始树如下图所示。
每个查询应该按以下方式处理。
- 第一个查询询问你顶点$2$和顶点$3$之间的距离。按顺序走边$1$和边$2$,它们之间的路径的总权重为$9$,这是最小的,所以你应该打印$9$。
- 第二个查询询问你顶点$1$和顶点$5$之间的距离。按顺序走边$3$和边$4$,它们之间的路径的总权重为$19$,这是最小的,所以你应该打印$19$。
- 第三个查询将边$3$的权重改为$1$。
- 第四个查询询问你顶点$1$和顶点$5$之间的距离。按顺序走边$3$和边$4$,它们之间的路径的总权重为$11$,这是最小的,所以你应该打印$11$。
样例输入 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
样例输出 2
5000000000 4294967296
注意答案可能不适用$32$位整数。
样例输入 3
1 1 2 1 1
样例输出 3
0
样例输入 4
8 1 2 105 1 3 103 2 4 105 2 5 100 5 6 101 3 7 106 3 8 100 18 2 2 8 2 3 6 1 4 108 2 3 4 2 3 5 2 5 5 2 3 1 2 4 3 1 1 107 2 3 1 2 7 6 2 3 8 2 1 5 2 7 6 2 4 7 2 1 7 2 5 3 2 8 6
样例输出 4
308 409 313 316 0 103 313 103 525 100 215 525 421 209 318 519