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:
CHANGE i v
|
Change the weight of the ith edge to v |
NEGATE a b
|
Negate the weight of every edge on the path from a to b |
QUERY a 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 b with 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
1 3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
Sample Output
1
3
Source
POJ Monthly--2007.06.03, Lei, Tao
【分析】
好久没写了。
写一道练练手。
/*
宋代苏轼
《南乡子·重九涵辉楼呈徐君猷》
霜降水痕收。浅碧鳞鳞露远洲。酒力渐消风力软，飕飕。破帽多情却恋头。
佳节若为酬。但把清尊断送秋。万事到头都是梦，休休。明日黄花蝶也愁。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int INF = 0x3f3f3f3f;
const int maxn= + ;
const int maxnode = ;
const int maxm= * + ;
using namespace std;
struct Node{//权值线段树
int l, r;
int Max, Min;
bool neg;//取反标记
}tree[maxn * ];
struct Edge{
int u, v, w;
}edges[maxn];//输入的边 int n, fa[maxn], size[maxn];
int son[maxn], dep[maxn], top[maxn];
int pos[maxn], Time;
int M, head[maxn], next[maxm], to[maxm], w[maxm]; //第一次dfs
void dfs_1(int u){
size[u] = ;
son[u] = ;
for (int i = head[u]; i != -; i = next[i]){
int v = to[i];
if (v == fa[u]) continue;
dep[v] = dep[u] + ;
fa[v] = u;
dfs_1(v);
size[u] += size[v];
if (size[v] > size[son[u]]) son[u] = v;
}
return;
}
void dfs_2(int u, int top_node){
top[u] = top_node;
pos[u] = ++Time;//给他和他的父亲的边在线段树中的位置
//重边
if (son[u]) dfs_2(son[u], top_node);
//轻边
for (int i = head[u]; i != -; i = next[i]){
int v = to[i];
if (v == fa[u] || v == son[u]) continue;
dfs_2(v, v);
}
}
//建树
void build(int x, int l, int r){
tree[x].l = l;tree[x].r = r;
tree[x].Max = -INF;
tree[x].Min = INF;
tree[x].neg = ;
if (l == r) return; int mid = (l + r) >> ;
build(x << , l, mid);
build((x << ) | , mid + , r);
}
void update(int x){
tree[x].Max = max(tree[x << ].Max, tree[(x << ) | ].Max);
tree[x].Min = min(tree[x << ].Min, tree[(x << ) | ].Min);
return;
}
//标记下传
void pushdown(int x){
if (tree[x].l == tree[x].r) return; if (tree[x].neg){
int l = (x << ), r = l | ;
tree[l].neg ^= ;
tree[l].Min *= -;
tree[l].Max *= -;
swap(tree[l].Min, tree[l].Max); tree[r].neg ^= ;
tree[r].Min *= -;
tree[r].Max *= -;
swap(tree[r].Min, tree[r].Max); tree[x].neg = ;
}
}
//在线段树中修改l,r为val
void change2(int x, int l, int r, int val){
pushdown(x);
if (tree[x].l == l && tree[x].r == r){
if (val == INF){//取反操作,注意已经pushdown过了
tree[x].neg = ;
tree[x].Min *= -;
tree[x].Max *= -;
swap(tree[x].Min, tree[x].Max);
} else tree[x].Min = tree[x].Max = val;//更新val
return;
} int mid = (tree[x].l + tree[x].r) >> ;
if (r <= mid) change2(x << , l, r, val);
else if (l > mid) change2((x << ) | , l, r, val);
else{
change2(x << , l, mid, val);
change2((x << ) | , mid + , r, val);
}
update(x);
}
int query2(int x, int l, int r){
pushdown(x);
if (tree[x].l == l && tree[x].r == r) return tree[x].Max; int mid = (tree[x].l + tree[x].r) >> ;
if (r <= mid) return query2(x << , l, r);
else if (l > mid) return query2((x << ) | , l, r);
else return max(query2((x << ), l, mid), query2((x << ) | , mid + , r));
}
//树链剖分部分
void change(int x, int y, int v){
while (top[x] != top[y]){
//总是矮的往上爬..
//保证dep[top[x]] >= dep[top[y]]
if (dep[top[x]] < dep[top[y]]) swap(x, y); change2(, pos[top[x]], pos[x], v);
x = fa[top[x]];
} if (x == y) return;
if (dep[x] > dep[y]) swap(x, y);
change2(, pos[son[x]], pos[y], v);
}
int query(int x, int y){
int Ans = -INF;
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]]) swap(x, y); Ans = max(Ans, query2(, pos[top[x]], pos[x]));
x = fa[top[x]];
}
if (x == y) return Ans;
if (dep[x] > dep[y]) swap(x, y);
Ans = max(Ans, query2(, pos[son[x]], pos[y]));
return Ans == -INF ? : Ans;
}
void work(){
while(){
char str[];
scanf("%s", str);
if(str[] == 'C'){
int x, v;
scanf("%d%d", &x, &v);
change2(, pos[edges[x].v], pos[edges[x].v], v);
}else if(str[] == 'N'){
int l, r;
scanf("%d%d", &l, &r);
change(l, r, INF);
}else if(str[] == 'Q'){//询问两点之间最大值
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}else break;
}
}
//加边
void addEdge(int u, int v, int c){
to[M] = v;
w[M] = c;
next[M] = head[u];
head[u] = M++;
}
void init(){
memset(head, -, sizeof(head));//邻接表初始化
memset(dep, , sizeof(dep));
M = Time = ;//总边数和时间
fa[] = size[] = ;
//加边
scanf("%d", &n);
for (int i = ; i < n; i++){
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
addEdge(edges[i].u, edges[i].v, edges[i].w);
addEdge(edges[i].v, edges[i].u, edges[i].w);
}
dfs_1();
dfs_2(, );
build(, , Time);
for (int i = ; i < n; i++){
int x = edges[i].u, y = edges[i].v;
//判断父亲
if (dep[x] > dep[y]) swap(edges[i].u, edges[i].v);
//u一定是父亲
change2(, pos[edges[i].v], pos[edges[i].v], edges[i].w);
}
} int main(){
int T; scanf("%d", &T);
while (T--){
init();
work();
}
//printf("%d\n", INF);
return ;
}