POJ 3237:Tree

正文索引 [隐藏]

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

CHANGEi v Change the weight of the ith edge to v
NEGATEa b Negate the weight of every edge on the path from a to b
QUERYa b Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.
Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and bwith weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

Sample Output

题目大意

给你一颗树,要求支持下列3个操作:
1.Q-询问两点之间路径的边中边权最大的;
2.N-把两点之间的路径的边权全部取反;
3.C-修改某条边的边权。

题解

这道题目用树链剖分,才开始学习树链剖分,这一题调了许久,结果最后发现是Query线段树的Tag没有下传。
这道题线段树只需要维护一下最大值和最小值,然后取反操作就是最大值和最小值都取反,然后交换最大值最小值【稍微脑补一下】

代码