Sengxian's Blog

//  Created by Sengxian on 3/16/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Spoj QTREE IV 链分治
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar(); bool flag = false;
    while(!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int maxn = 100000 + 3, INF = 0x3f3f3f3f;
struct edge {
    int to, cost;
    edge(int to, int cost): to(to), cost(cost) {}
};
vector<edge> G[maxn];
int n = 0, blackCnt = 0;
bool color[maxn]; // 0 - black 1 - white

//datas
int fa[maxn], fv[maxn], s[maxn], id[maxn], idR[maxn], bel[maxn], timestamp = 0, sz[maxn]; //sz[i] 为以 i 为根的线段树的大小
int sum[maxn]; //线段树的区间和
int root[maxn]; //链头的线段树节点标号
//end

//seg dates
static const int maxNode = (1 << 17) * 2 + 10;
struct Node {
    int maxL, maxR, opt;
    Node(int maxL = -INF, int maxR = -INF, int opt = -INF): maxL(maxL), maxR(maxR), opt(opt) {} 
}segs[maxNode];
int ls[maxNode], rs[maxNode];
int segCnt = 0;
//end

template <typename T>
struct Rint {
    bool operator()(const T &l , const T &r) const {return l > r;}
};
multiset<int, Rint<int> > ch[maxn], ans;

int dfs1(int u, int f) {
    fa[u] = f, s[u] = 1;
    for (int i = 0; i < (int)G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != f) {
            fv[e.to] = e.cost;
            s[u] += dfs1(e.to, u);
        }
    }
    return s[u];
}

void dfs2(int u, int num) {
    idR[timestamp] = u, id[u] = timestamp++, bel[u] = num;
    sz[num]++;
    int Max = 0, idx = -1;
    for (int i = 0; i < (int)G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != fa[u] && s[e.to] > Max) {Max = s[e.to], idx = e.to;}
    }
    if (Max == 0) return;
    dfs2(idx, num);
    for (int i = 0; i < (int)G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != fa[u] && e.to != idx) dfs2(e.to, e.to);
    }
}

Node merge(const Node &ln, const Node &rn, int dL, int dMid ,int dR) {
    Node newNode;
    newNode.maxL = max(ln.maxL, dL + rn.maxL);
    newNode.maxR = max(rn.maxR, dR + ln.maxR);
    newNode.opt = max(max(ln.opt, rn.opt), dMid + ln.maxR + rn.maxL);
    return newNode;
}

void maintain(int o, int u) {
    int d1 = -INF, d2 = -INF;
    if (color[u] == 0) d1 = d2 = 0;
    if (ch[u].size()) d1 = max(d1, *(ch[u].begin()));
    if (ch[u].size() > 1) d2 = max(d2, *(++ch[u].begin()));
    segs[o].maxL = segs[o].maxR = d1;
    segs[o].opt = d1 + d2;
    if (color[u] == 0) segs[o].opt = max(segs[o].opt, 0);
}

void buildTree(int o, int l, int r) {
    //cout << o << ' ' << l << ' ' << r << endl;
    if(r - l == 1) {
        int u = idR[l];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            edge &e = G[u][i];
            if (e.to != fa[u] && bel[e.to] != bel[u]) {
                buildTree(root[e.to] = segCnt++, id[e.to], id[e.to] + sz[e.to]);
                ch[u].insert(segs[root[e.to]].maxL + e.cost);
                ans.insert(segs[root[e.to]].opt);
            }
        }
        maintain(o, u);
    }else {
        int mid = (l + r) / 2;
        buildTree(ls[o] = segCnt++, l, mid);
        buildTree(rs[o] = segCnt++, mid, r);
        segs[o] = merge(segs[ls[o]], segs[rs[o]], sum[mid] - sum[l], sum[mid] - sum[mid - 1], sum[r - 1] - sum[mid - 1]);
    }
}

vector<int> path;
void findPath(int u) {
    while (u != -1) {
        path.push_back(u);
        u = fa[bel[u]];
    }
}

void modify(int o, int l, int r, int idx) {
    if (r - l == 1) {
        if (idx + 1 != path.size()) {
            int nexT = bel[path[idx + 1]], u = idR[l];
            ans.erase(ans.find(segs[root[nexT]].opt));
            ch[u].erase(ch[u].find(segs[root[nexT]].maxL + fv[nexT]));
            modify(root[nexT], id[nexT], id[nexT] + sz[nexT], idx + 1);
            ch[u].insert(segs[root[nexT]].maxL + fv[nexT]);
            ans.insert(segs[root[nexT]].opt);
        }
        maintain(o, idR[l]);
    }else {
        int u = path[idx], mid = (l + r) / 2;
        if (id[u] < mid) modify(ls[o], l, mid, idx);
        else modify(rs[o], mid, r, idx);
        segs[o] = merge(segs[ls[o]], segs[rs[o]], sum[mid] - sum[l], sum[mid] - sum[mid - 1], sum[r - 1] - sum[mid - 1]);
    }
}

void process() {
    dfs1(0, -1);
    dfs2(0, 0);
//    for (int i = 0; i < n; ++i)
//        cout << i << ' ' << bel[i] << endl;
    for (int i = 0; i < n; ++i)
        sum[id[i]] = fv[i];
    for (int i = 1; i < n; ++i)
        sum[i] += sum[i - 1];
    buildTree(root[0] = segCnt++, id[0], id[0] + sz[0]);
}

char op[2];
int main() {
    //freopen("test.in", "r", stdin);
    n = ReadInt();
    memset(color, 0, sizeof(bool) * n);
    blackCnt = n;
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1, c = ReadInt();
        G[f].push_back(edge(t, c));
        G[t].push_back(edge(f, c));
    }
    process();
    int q = ReadInt();
    while (q--) {
        scanf("%s", op);
        if (op[0] == 'C') {
            int u = ReadInt() - 1;
            if (color[u]) blackCnt++;
            else blackCnt--;
            color[u] = !color[u];
            path.clear();
            findPath(u);
            reverse(path.begin(), path.end());
            modify(root[0], id[0], id[0] + sz[0], 0);
        }else if(op[0] == 'A') {
            if (blackCnt == 0) puts("They have disappeared.");
            else printf("%d\n", max(*ans.begin(), segs[0].opt));
        }else assert(false);
    }
    return 0;
}