OI题库

【题目描述】

给你由N个结点组成的树。树的节点被编号为1到N，边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一：

CHANGE i v：将第i条边的权值改成v。

NEGATE a b：将点a到点b路径上所有边的权值变成其相反数。

QUERY a b：找出点a到点b路径上各边的最大权值。

【输入格式】

输入文件的第一行有一个整数N（N<=10000）。

接下来N-1行每行有三个整数a,b,c，代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。

接下来是若干条指令（不超过10^5条），都按照上面所说的格式。

输入文件的最后一行是"DONE".

【输出格式】

对每个“QUERY”指令，输出一行，即路径上各边的最大权值。

【样例输入】

3

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

【样例输出】

1

3

【提示】

这里的输入输出格式和POJ上原题略有不同。

【来源】

POJ 3237 Tree