题目背景

数据规模和spoj上有所不同

题目描述

给定一棵n个节点的树，有两个操作：

CHANGE i ti 把第i条边的边权变成ti
QUERY a b 输出从a到b的路径中最大的边权，当a=b的时候，输出0

输入输出格式

输入格式：

第一行输入一个n，表示节点个数

第二行到第n行每行输入三个数，ui，vi，wi，分别表示 ui，vi有一条边，边权是wi

第n+1行开始，一共有不定数量行，每一行分别有以下三种可能

CHANGE，QUERY同题意所述

DONE表示输入结束

输出格式：

对于每个QUERY操作，输出一个数，表示a b之间边权最大值

输入输出样例

输入样例#1：复制

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

输出样例#1：复制

1
3

说明

数据保证：

1 $\leq$ n $\leq$ $10^5$

操作次数 $\leq$ $3*10^5$

wi和ti $\leq$ $2^{31}-1$

$树链剖分裸题，套一个线段树维护就好了。需要注意代码细节，比如节点编号要映射到序列上，但是直接用了节点编号修改的错误。$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 5;
struct edge {
	int v, w, next;
}e[maxn << 1];
int head[maxn], cnt, n, a, b, c, t, f;
char s;
inline char gc(){
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
    x = 0; static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}
inline void rc(char & x) {
    x = gc();
    while(x != 'Q' && x != 'C' && x != 'D') x = gc();;
}
void adde(const int &u, const int &v, const int &w) {
	e[++cnt] = (edge) {v, w, head[u]};
	head[u] = cnt;
}
int fa[maxn], son[maxn], size[maxn], id[maxn], d[maxn], top[maxn];
int idcnt, num[maxn], ni[maxn], ow[maxn];
void dfs1(int u, int p) {
	fa[u] = p, d[u] = d[p] + 1;
	size[u] = 1;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		dfs1(v, u), size[u] += size[v], ow[v] = e[i].w;
		ni[((i + 1) >> 1)] = v;
		if(size[v] > size[son[u]]) son[u] = v;
	}
}
void dfs2(int u, int tp) {
	top[u] = tp, id[u] = ++idcnt, num[idcnt] = ow[u];
	if(son[u]) dfs2(son[u], tp);
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
namespace SGT {
	int mx[maxn << 2], cnt;
	void push_up(int rt) {mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);}
	void build(int l, int r, int rt) {
		if(l == r) {mx[rt] = num[l];return ;}
		int mid = l + r >> 1;
		build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
		push_up(rt);
	}
	void edit(int pos, int tl, int tr, int dt, int rt) {
		if(tl == tr) {num[tl] = dt, mx[rt] = dt;return ;}
		int mid = tl + tr >> 1;
		if(pos <= mid) edit(pos, tl, mid, dt, rt << 1);
		else edit(pos, mid + 1, tr, dt, rt << 1 | 1);
		push_up(rt);
	}
	int query(int l, int r, int tl, int tr, int rt) {
		if(l == tl && r == tr) return mx[rt];
		int mid = tl + tr >> 1;
		if(r <= mid) return query(l, r, tl, mid, rt << 1);
		else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
		else return max(query(l, mid, tl, mid, rt << 1), query(mid + 1, r, mid + 1, tr, rt << 1 | 1));
	}
}
#define Q(l, r) query((l), (r), 1, n, 1)
int Gmax(int u, int v) {
	using namespace SGT;
	int ans = 0;
	while(top[u] != top[v]) {
		if(d[top[u]] < d[top[v]]) swap(u, v);
		ans = max(ans, Q(id[top[u]], id[u])), u = fa[top[u]];
	}
	if(d[u] > d[v]) ans = max(ans, Q(id[v] + 1, id[u]));
	if(d[v] > d[u]) ans = max(ans, Q(id[u] + 1, id[v]));
	return ans;
}
int main() {
	read(n);
	for(register int i = 1; i < n; ++i) {
		read(a), read(b), read(c);
		adde(a, b, c), adde(b, a, c);
	}
	dfs1(1, 0), dfs2(1, 1);
	SGT::build(1, n, 1);
	while(1) {
		rc(s);
		if(s == 'D') break;
		read(a), read(b);
		if(s == 'Q') printf("%d\n", Gmax(a, b));
		else SGT::edit(id[ni[a]], 1, idcnt, b, 1);
	}
	return 0;
}

Rockdu's Blog