[SPOJ]Query on a tree（树链剖分，线段树）

题目链接：http://www.spoj.com/problems/QTREE/en/

照着集训队论文敲的…万幸树剖部分没写错…

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, p) memset((a), (p), sizeof(a))
#define Full(a) memset((a), 0x7f7f7f, sizeof(a))
#define lrt rt << 1
#define rrt rt << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(p) p & (-p)
#define onenum(p) __builtin_popcount(p)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<LL, LL> pll;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb;

typedef struct Edge {
    int v, w;
    Edge() {}
    Edge(int vv, int ww) : v(vv), w(ww) {}
}Edge;
const int maxn = 10100;
int n, k;
int depth[maxn];    //点的深度
int siz[maxn];        //以该点为树根，子树的点数
int fa[maxn];            //父亲节点编号
int son[maxn];        //重儿子编号
int top[maxn];        //点所在的重链的顶端节点
int p[maxn];            //点与其父亲节点的连边在线段树中的位置
int pos;
vector<Edge> G[maxn];
char cmd[15];

int dfs1(int p, int u, int d) {
    siz[u] = 1; depth[u] = d; fa[u] = p;
    Rep(i, G[u].size()) {
        int& v = G[u][i].v;
        if(v == p) continue;
        siz[u] += dfs1(u, v, d+1);
        if(son[u] == -1 || siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
    return siz[u];
}

void dfs2(int u, int tp) {
    top[u] = tp; p[u] = ++pos;
    if(son[u] != -1) dfs2(son[u], top[u]);
    Rep(i, G[u].size()) {
        int& v = G[u][i].v;
        if(v != son[u] && v != fa[u]) {
            dfs2(v, v);
        }
    }
}

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int sum[maxn<<2];

void pushUP(int rt) {
    sum[rt] = max(sum[rt<<1], sum[rt<<1|1]);
}

void build(int l, int r, int rt) {
    sum[rt] = 0;
    if(l == r) return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushUP(rt);
}

void update(int p, int x, int l, int r, int rt) {
    if(l == r) {
        sum[rt] = x;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) update(p, x, lson);
    else update(p, x, rson);
    pushUP(rt);
}

int query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) return sum[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret = max(ret, query(L, R, lson));
    if(R > m) ret = max(ret, query(L, R, rson));
    return ret;
}

int find(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int tmp = 0;
    while(f1 != f2) {
        if(depth[f1] < depth[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        tmp = max(tmp, query(p[f1], p[u], 1, pos, 1));
        u = fa[f1];
        f1 = top[u];
    }
    if(u == v) return tmp;
    if(depth[u] > depth[v]) swap(u, v);
    return max(tmp, query(p[son[u]], p[v], 1, pos, 1));
}

int e[maxn][3];

signed main() {
    // FRead();
    int T, u, v, w;
    Rint(T);
    W(T) {
        Rint(n);
        For(i, 1, n+5) G[i].clear();
        Cls(siz); Cls(depth); Clr(son, -1); Clr(fa, -1); pos = 0; Cls(sum);
        Rep(i, n-1) {
            Rint(u); Rint(v); Rint(w);
            G[u].push_back(Edge(v, w));
            G[v].push_back(Edge(u, w));
            e[i+1][0] = u; e[i+1][1] = v; e[i+1][2] = w;
        }
        dfs1(-1, 1, 0);
        dfs2(1, 1);
        build(1, pos, 1);
        For(i, 1, n) {
            u = e[i][0]; v = e[i][1]; w = e[i][2];
            if(depth[u] > depth[v]) {
                swap(e[i][0], e[i][1]);
                swap(u, v);
            }
            update(p[v], w, 1, pos, 1);
        }
        while(~Rs(cmd) && cmd[0] != 'D') {
            Rint(u); Rint(v);
            if(cmd[0] == 'Q') {
                printf("%d
", find(u, v));
            }
            if(cmd[0] == 'C') {
                update(p[e[u][1]], v, 1, pos, 1);
            }
        }
    }
    RT 0;
}