题目详情题解（0）讨论（0）提交记录（0）

AT_abc294_g.[ABC294G] Distance Queries on a Tree

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一颗有 nn 个节点的树，带边权，要进行 QQ 次操作，操作有两种：

1 i w：将第 ii 条边的边权改为 ww。
2 u v：询问 u,vu,v 两点的距离。

输入格式

第一行，一个正整数 nn。
接下来 n−1n-1 行，每行三个数 u,v,wu,v,w，表示一条树边。
接下来一个正整数 QQ。
接下来 QQ 行，每行三个数，描述一个询问，格式如上。

输出格式

对于每个 22 操作，输出一行一个数，表示该询问的答案。

输入输出样例

  • 输入#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

    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

  • 输入#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

说明/提示

1≤n,Q≤2×105，1≤wi≤1091\le n,Q\le 2\times10^5，1\le w_i\le 10^9

输入解题思路，AI测评打分。不知道怎么写?

首页