# SP375 QTREE - Query on a tree

• 167通过
• 1.8K提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 最近公共祖先,LCA 树链剖分,树剖 线段树
• 难度 NOI/NOI+/CTSC
• 时空限制 851ms / 1536MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

给定n个点的树，边按输入顺序编号为1,2,...n-1，要求作以下操作： CHANGE i ti 将第i条边权值改为ti QUERY a b 询问从a点到b点路径上的最大边权

有多组测试数据，每组数据以DONE结尾

感谢@vegacx 提供的翻译

## 题目描述

You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

We will ask you to perfrom some instructions of the following form:

• CHANGE i ti : change the cost of the i-th edge to ti
or
• QUERY a b : ask for the maximum edge cost on the path from node a to node b

## 输入输出格式

输入格式：

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000),
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
• The next lines contain instructions "CHANGE i ti" or "QUERY a b",
• The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

输出格式：

For each "QUERY" operation, write one integer representing its result.

## 输入输出样例

输入样例#1： 复制
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
输出样例#1： 复制
1
3
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。