记录编号	416340	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.142 s
提交时间	2017-06-21 09:46:30	内存使用	0.91 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 1e4 + 10;
const int INF = 0x7fffffff;

inline char getc(void){
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int in(void){
    register char tmp = getc();
    register int res = 0, f = 1;
    while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
    if(tmp == '-') f = -1, tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res * f;
}

struct EDGE{
    int val, to;
    int ne;

    EDGE(){;}
    EDGE(int _val, int _to, int _ne){
        val = _val, to = _to, ne = _ne;
    }
};

struct NODE{
    int mx;
    NODE *ls, *rs;

    NODE(){
        ls = rs = NULL;
    }
};

inline void add_edge(int fr, int to, int val);
inline int get_cmd(void);
void dfs(int u);
void dfs(int u, int tp);
NODE* Build(int l, int r);
void update(NODE *node, int w, int k, int L, int R);
inline int LCA(int a, int b);

vector<EDGE> edge;
int head[MAXN];
int top[MAXN], fat[MAXN], siz[MAXN], dep[MAXN];
int fa[MAXN], val[MAXN];
int dfn[MAXN], id[MAXN];
int N;
NODE *root;

int main(){ 
#ifndef LOCAL
    freopen("qtree.in", "r", stdin);
    freopen("qtree.out", "w", stdout);
#endif
    memset(head, 0xff, sizeof(head));

    N = in();
    for(int i = 1, a, b, c; i < N; ++i){
        a = in(), b = in(), c = in();
        add_edge(a, b, c);
    }
    val[1] = -INF;
    dep[1] = 1;
    dfs(1);
    dfs(1, 1);

    root = Build(1, N);

    register int cmd;
    while((cmd = get_cmd())){
        register int a = in(), b = in();
        if(cmd == 1) cout<<LCA(a, b)<<'\n';
        else {
            register int c = edge[(a << 1) - 1].to, d = edge[(a - 1) << 1].to;
            if(fa[c] == d) update(root, dfn[c], b, 1, N);
            else update(root, dfn[d], b, 1, N);
        }
    }

    return 0;
}

inline void add_edge(int fr, int to, int val){
    edge.push_back(EDGE(val, to, head[fr])), head[fr] = edge.size() - 1;
    edge.push_back(EDGE(val, fr, head[to])), head[to] = edge.size() - 1;
    return ;
}

inline int get_cmd(void){
    register char cmd = getc();
    while(cmd ^ 'Q' && cmd ^ 'C' && cmd ^ 'D') cmd = getc();
    if(cmd == 'Q') return 1;
    if(cmd == 'C') return 2;
    return 0;
}

void dfs(int u){
    register int v;
    siz[u] = 1;

    for(register int e = head[u]; ~e; e = edge[e].ne){
        if(dep[v = edge[e].to]) continue;
        fa[v] = u;
        val[v] = edge[e].val;
        dep[v] = dep[u] + 1;
        dfs(v);
        siz[u] += siz[v];

        if(siz[v] > siz[fat[u]]) fat[u] = v;
    }

    return ;
}

void dfs(int u, int tp){
    static int cnt = 0;
    register int v;
    
    id[dfn[u] = ++cnt] = u;
    top[u] = tp;
    if(!fat[u]) return ;
    dfs(fat[u], tp);

    for(register int e = head[u]; ~e; e = edge[e].ne){
        if(dfn[v = edge[e].to]) continue;
        dfs(v, v);
    }

    return ;
}

NODE* Build(int l, int r){
    register NODE *p = new NODE();

    if(l ^ r){
        register int mid = (l + r) >> 1;
        p->ls = Build(l, mid);
        p->rs = Build(mid + 1, r);
        p->mx = max(p->ls->mx, p->rs->mx);
    } else p->mx = val[id[l]];

    return p;
}

void update(NODE *node, int w, int k, int L, int R){
    if(L == R){
        node->mx = k;
        return ;
    }
    register int mid = (L + R) >> 1;
    if(w <= mid) update(node->ls, w, k, L, mid);
    else update(node->rs, w, k, mid + 1, R);

    node->mx = max(node->ls->mx, node->rs->mx);

    return ;
}

int Query(NODE *node, int l, int r, int L, int R){
    if(l == L && r == R) return node->mx;

    register int mid = (L + R) >> 1;
    if(r <= mid) return Query(node->ls, l, r, L, mid);
    if(mid < l) return Query(node->rs, l, r, mid + 1, R);
    return max(Query(node->ls, l, mid, L, mid), Query(node->rs, mid + 1, r, mid + 1, R));
}

inline int LCA(int a, int b){
    register int ta = top[a], tb = top[b];
    register int ans = -INF;

    while(ta ^ tb){
        if(dep[ta] > dep[tb]){
            register int tmp;
            tmp = a, a = b, b = tmp;
            tmp = ta, ta = tb, tb = tmp;
        }
        ans = max(ans, Query(root, dfn[tb], dfn[b], 1, N));
        b = fa[tb];
        tb = top[b];
    }

    if(dep[a] > dep[b]) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    if(a == b) return ans;
    return max(ans, Query(root, dfn[a] + 1, dfn[b], 1, N));
}