题意：给出n个点n-1条边的树，有两个操作，一个是查询节点l到r的边的最大值，然后指定边的更改权值。

题解：差不多是树链剖分的模版题，注意每个点表示的边是连向其父亲节点的边。

#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 1e4 + 10;struct Edge {    int v , next;}edge[M << 1];int head[M] , e;int top[M];int fa[M];int p[M];int fp[M];int son[M];int deep[M];int num[M];int pos;void init() {    memset(head , -1 , sizeof(head));    memset(son , -1 , sizeof(son));    e = 0;    pos = 0;}void add(int u , int v) {    edge[e].v = v;    edge[e].next = head[u];    head[u] = e++;}void dfs1(int u , int pre , int d) {    deep[u] = d;    fa[u] = pre;    num[u] = 1;    for(int i = head[u] ; i != -1 ; i = edge[i].next) {        int v = edge[i].v;        if(v != pre) {            dfs1(v , u , d + 1);            num[u] += num[v];            if(son[u] == -1 || num[son[u]] < num[v])                son[u] = v;        }    }}void getpos(int u , int sp) {    top[u] = sp;    p[u] = pos++;    fp[p[u]] = u;    if(son[u] == -1)        return ;    getpos(son[u] , sp);    for(int i = head[u] ; i != -1 ; i = edge[i].next) {        int v = edge[i].v;        if(son[u] != v && v != fa[u]) {            getpos(v , v);        }    }}struct TnT {    int l , r , MAX;}T[M << 2];void pushup(int i) {    T[i].MAX = max(T[i << 1].MAX , T[(i << 1) | 1].MAX);}void build(int l , int r , int i) {    int mid = (l + r) >> 1;    T[i].l = l , T[i].r = r , T[i].MAX = 0;    if(T[i].l == T[i].r)        return ;    build(l , mid , i << 1);    build(mid + 1 , r , (i << 1) | 1);    pushup(i);}void updata(int pos , int i , int ad) {    int mid = (T[i].l + T[i].r) >> 1;    if(T[i].l == pos && T[i].r == pos) {        T[i].MAX = ad;        return ;    }    if(mid < pos) {        updata(pos , (i << 1) | 1 , ad);    }    else {        updata(pos , i << 1 , ad);    }    pushup(i);}int query(int l , int r , int i) {    int mid = (T[i].l + T[i].r) >> 1;    if(T[i].l == l && T[i].r == r) {        return T[i].MAX;    }    pushup(i);    if(mid < l) {        return query(l , r , (i << 1) | 1);    }    else if(mid >= r) {        return query(l , r , i << 1);    }    else {        return max(query(l , mid , i << 1) , query(mid + 1 , r , (i << 1) | 1));    }}int find(int u , int v) {    int f1 = top[u] , f2 = top[v];    int tmp = 0;    while(f1 != f2) {        if(deep[f1] < deep[f2]) {            swap(f1 , f2);            swap(u , v);        }        tmp = max(tmp , query(p[f1] , p[u] , 1));        u = fa[f1] , f1 = top[u];    }    if(u == v) return tmp;    if(deep[u] > deep[v]) swap(u , v);    return max(tmp , query(p[son[u]] , p[v] , 1));}int ed[M][3];int main() {    int t , n , u , v;    scanf("%d" , &t);    while(t--) {        scanf("%d" , &n);        init();        for(int i = 0 ; i < n - 1 ; i++) {            for(int j = 0 ; j < 3 ; j++) {                scanf("%d" , &ed[i][j]);            }            add(ed[i][0] , ed[i][1]);            add(ed[i][1] , ed[i][0]);        }        dfs1(1 , 0 , 0);        getpos(1 , 1);        build(0 , pos , 1);        for(int i = 0 ; i < n - 1 ; i++) {            if(deep[ed[i][0]] > deep[ed[i][1]])                swap(ed[i][0] , ed[i][1]);            updata(p[ed[i][1]] , 1 , ed[i][2]);        }        char cp[10];        while(scanf("%s" , cp)) {            if(cp[0] == ‘D‘)                break;            scanf("%d%d" , &u , &v);            if(cp[0] == ‘C‘) {                updata(p[ed[u - 1][1]] , 1 , v);            }            else {                printf("%d\n" , find(u , v));            }        }    }    return 0;}

SPOJ - QTREE（树链剖分+单点更新+区间最大值查询）