/* ID: espr1t TASK: KEYWORDS: */ #include #include #include #include #include #include #include #include using namespace std; FILE *in; FILE *out; mt19937 mt; int randd() { int ret = mt(); return ret < 0 ? -ret : ret; } const int MAX = 100001; const int TREE = 524288; const int INF = 1000000001; const int DIST = 1000; const int RAND = 0; struct Node { int node, level; bool operator < (const Node& r) const { return level != r.level ? level < r.level : node < r.node; } }; struct Edge { int to, price; Edge(int to_ = 0, int price_ = 0) : to(to_), price(price_) {} }; int n; int level[MAX], sum[MAX], parent[MAX]; int nextIndex = 0; int order[MAX * 2]; Node tree[TREE]; int first[MAX], last[MAX]; vector v[MAX]; Node query(int idx1, int idx2) { idx1 += TREE / 2, idx2 += TREE / 2; if (idx1 == idx2) return tree[idx1]; Node ret = tree[idx1]; ret = min(ret, tree[idx1]); bool flag1 = !(idx1 & 1); idx1 >>= 1; ret = min(ret, tree[idx2]); bool flag2 = (idx2 & 1); idx2 >>= 1; while (idx1 != idx2) { if (flag1) ret = min(ret, tree[(idx1 << 1) + 1]); if (flag2) ret = min(ret, tree[(idx2 << 1) + 0]); flag1 = !(idx1 & 1); idx1 >>= 1; flag2 = (idx2 & 1); idx2 >>= 1; } return ret; } Node lca(int node1, int node2) { int left = min(first[node1], first[node2]); int right = max(last[node1], last[node2]); return query(left, right); } void getOrder() { memset(first, -1, sizeof(first)); stack < pair > s; s.push(make_pair(1, 0)); while (!s.empty()) { int node = s.top().first; int upto = s.top().second; if (first[node] == -1) { first[node] = nextIndex; } last[node] = nextIndex; order[nextIndex++] = node; while (upto < (int)v[node].size() && level[node] > level[v[node][upto].to]) upto++; if (upto < (int)v[node].size()) { s.top().second = upto + 1; s.push(make_pair(v[node][upto].to, 0)); continue; } s.pop(); } } void buildTree() { getOrder(); for (int i = 0; i < nextIndex; i++) { tree[TREE / 2 + i].node = order[i]; tree[TREE / 2 + i].level = level[order[i]]; } for (int i = TREE / 2 + nextIndex; i < TREE; i++) tree[i].node = -1, tree[i].level = INF; for (int i = TREE / 2 - 1; i > 0; i--) { tree[i] = min(tree[i * 2 + 0], tree[i * 2 + 1]); } } void getLevels() { memset(level, 63, sizeof(level)); queue q; q.push(1); level[1] = 1, sum[1] = 0, parent[1] = -1; while (!q.empty()) { int node = q.front(); q.pop(); for (int i = 0; i < (int)v[node].size(); i++) { if (level[v[node][i].to] > level[node] + 1) { level[v[node][i].to] = level[node] + 1; sum[v[node][i].to] = sum[node] + v[node][i].price; parent[v[node][i].to] = node; q.push(v[node][i].to); } } } } deque spec; int specPos[MAX]; int main(void) { in = stdin; out = stdout; in = fopen("voyage.in", "rt"); out = fopen("voyage.out", "wt"); fscanf(in, "%d", &n); for (int i = 0; i < n - 1; i++) { int node1, node2, price; fscanf(in, "%d %d %d", &node1, &node2, &price); v[node1].push_back(Edge(node2, price)); v[node2].push_back(Edge(node1, price)); } getLevels(); buildTree(); memset(specPos, -1, sizeof(specPos)); int q; fscanf(in, "%d", &q); for (int i = 0; i < q; i++) { int t; fscanf(in, "%d", &t); if (t == 0) { int node; fscanf(in, "%d", &node); if (specPos[node] == -1) { spec.push_back(node); specPos[node] = (int)spec.size() - 1; } else { int idx = specPos[node]; if (idx != (int)spec.size() - 1) { spec[idx] = spec.back(); specPos[spec[idx]] = idx; } spec.pop_back(); specPos[node] = -1; } } else { int node1, node2; fscanf(in, "%d %d", &node1, &node2); int anc = lca(node1, node2).node; //fprintf(stderr, "LCA of %d and %d is %d\n", node1, node2, anc); int lb1 = node1, ub1 = node1, idx1 = node1; for (int i = 0; i < DIST; i++) { if (specPos[idx1] != -1) { ub1 = idx1; if (specPos[lb1] == -1) lb1 = idx1; } if (idx1 == anc) break; idx1 = parent[idx1]; } int lb2 = node2, ub2 = node2, idx2 = node2; for (int i = 0; i < DIST; i++) { if (specPos[idx2] != -1) { ub2 = idx2; if (specPos[lb2] == -1) lb2 = idx2; } if (idx2 == anc) break; idx2 = parent[idx2]; } /* int maxTries = 100; for (int i = 0; i < RAND; i++) { if ((int)spec.size() > 0) { int which = spec[randd() % (int)spec.size()]; if (level[which] < level[anc]) { if (maxTries > 0) { maxTries--; i--; } continue; } if (level[which] > level[node1] - DIST + 1 && level[which] > level[node2] - DIST + 1) { if (maxTries > 0) { maxTries--; i--; } continue; } if (lca(which, anc).node != anc) continue; if (lca(node1, which).node == which) { if (specPos[lb1] == -1 || level[lb1] < level[which]) lb1 = which; if (specPos[ub1] == -1 || level[ub1] > level[which]) ub1 = which; } if (lca(node2, which).node == which) { if (specPos[lb2] == -1 || level[lb2] < level[which]) lb2 = which; if (specPos[ub2] == -1 || level[ub2] > level[which]) ub2 = which; } } } */ int ans = INF; if (specPos[ub1] == -1 && specPos[ub2] == -1) { ans = 0; } else if (specPos[ub1] != -1 && specPos[ub2] == -1) { ans = sum[lb1] - sum[ub1]; } else if (specPos[ub1] == -1 && specPos[ub2] != -1) { ans = sum[lb2] - sum[ub2]; } else { ans = sum[lb1] - sum[anc] + sum[lb2] - sum[anc]; } fprintf(out, "%d\n", ans); } } return 0; }