SPOJ – Query on Tree IV

命題

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.

All the nodes are white initially.

We will ask you to perfrom some instructions of the following form:

C a : change the color of node a.(from black to white or from white to black)
A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.


This is a solution in Divided on Edges Algorithm. The key section of this algorithm is build a binary tree on every node which add empty points inside. The nodes will turned to $O(2n)$ after.
There are some notes about the implement of the code (which is fantastic and amazing):

1. Add edges in pairs and use the pair number (id >> 1) to denote the things about this edge.
2. Use a guard to solve the boundary issues. Remember the $\infty$ is always a good choice, but do not let it overflow.

/** * @Author Kvar_ispw17 * @Date 2018.1.18 * @Problem SPOJ-QTREE4 * @Tag #Divided_on_Edge */ #include <cassert> #include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <queue> #pragma GCC optimize("-O2") using namespace std; typedef long long ll; template <typename _Tp> void read(_Tp &a, char c = 0, int op = 1) { for (c = getchar(); !isdigit(c); c = getchar()) if(c == '-') op = -1; for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= op; } const int N = (int)2e5 + 10; const int inf = 0x3f3f3f3f; int n, m, Q, color[N], pos[N]; int hd[N], tmp[N], nxt[4*N], to[4*N], w[4*N], tot; void add(int a, int b, int c) { nxt[++tot] = hd[a], to[hd[a] = tot] = b, w[tot] = c; nxt[++tot] = hd[b], to[hd[b] = tot] = a, w[tot] = c; } void add_tmp(int a, int b, int c) { nxt[++tot] = tmp[a], to[tmp[a] = tot] = b, w[tot] = c; nxt[++tot] = tmp[b], to[tmp[b] = tot] = a, w[tot] = c; assert(tot < 6 * n); } void build(vector<int> &ch, int fa, int l, int r) { if (l > r) return; if (l == r) { int e = ch[l]; add_tmp(fa, to[e], w[e]); return; } int u = ++n; color[u] = 1; int mid = (l + r) / 2; add_tmp(fa, u, 0); build(ch, u, l, mid); build(ch, u, mid + 1, r); } void reconstruct(int u, int fa) { vector<int> ch; for (int e = hd[u]; e != -1; e = nxt[e]) { int v = to[e]; if (v != fa) { reconstruct(v, u); ch.push_back(e); } } if (!ch.empty()) { int sz = (int)ch.size() - 1; int mid = sz / 2; build(ch, u, 0, mid); build(ch, u, mid + 1, sz); } } /* CAUTION : This class $data is used for multiple cases and have multiple means */ class data { public: int a, b; data() {} data(int a, int b) : a(a), b(b) {} bool operator < (const data &rhs) const { return a == rhs.a ? b < rhs.b : a < rhs.a; } bool operator > (const data &rhs) const { return a == rhs.a ? b > rhs.b : a > rhs.a; } }; int siz[N], del[N]; priority_queue<data> h[2*N]; /* $data represented -> { dis_to_root, node_id } */ vector<data> idx[N]; /* $data represented -> { HID, dis_to_root } */ data Heap[N]; /* $data represented -> { best_ans, idx } */ data find_center(int u, int fa, int sz) { siz[u] = 1; data ret = data(inf, -1); /* $data represented -> { bigger_sz, edge_id } */ for(int v, e = hd[u]; e != -1; e = nxt[e]) { if(del[e >> 1] || (v = to[e]) == fa) continue; ret = min(ret, find_center(v, u, sz)); siz[u] += siz[v]; ret = min(ret, data(max(siz[v], sz - siz[v]), e)); } return ret; } int tmp_sz; void dfs(int u, int fa, int dis, int ID) { tmp_sz++; if(color[u] == 0) h[ID].emplace(data(dis, u)); idx[u].emplace_back(data(ID, dis)); for(int e = hd[u]; e != -1; e = nxt[e]) { int v = to[e]; if(del[e >> 1] || v == fa) continue; dfs(v, u, dis + w[e], ID); } } void divide(int u, int sz) { int sz1, sz2; if(sz <= 1) return; int e = find_center(u, 0, sz).b; del[e >> 1] = true; tmp_sz = 0, h[e].emplace(data(-inf, -1)); dfs(to[e], 0, 0, e), sz1 = tmp_sz; tmp_sz = 0, h[e^1].emplace(data(-inf, -1)); dfs(to[e^1], 0, 0, e^1), sz2 = tmp_sz; Heap[e >> 1] = data(h[e].top().a + w[e] + h[e^1].top().a, e >> 1); divide(to[e], sz1); divide(to[e^1], sz2); } char op1[5], op; int x, a, b, c, white; void down(int u) { int i = u, j = i << 1 | 1; data t = Heap[i]; if(j + 1 < m && Heap[j + 1] > Heap[j]) j++; while(j < m && t < Heap[j]) { pos[Heap[j].b] = i; Heap[i] = Heap[j]; i = j, j = i << 1 | 1; if(j + 1 < m && Heap[j + 1] > Heap[j]) j++; } Heap[i] = t; pos[t.b] = i; } void up(int u) { int i = u, j = ((i + 1) >> 1) - 1; data t = Heap[i]; while(j >= 0 && Heap[j] < t) { pos[Heap[j].b] = i; Heap[i] = Heap[j]; i = j, j = ((i + 1) >> 1) - 1; } Heap[i] = t; pos[t.b] = i; } int main() { memset(tmp, -1, sizeof tmp); memset(hd, -1, sizeof hd); read(n), white = n; tot = n * 3; for (int i = 1; i < n; i++) read(a), read(b), read(c), add(a, b, c); tot = -1; reconstruct(1, 0); memcpy(hd, tmp, sizeof tmp); divide(1, n); m = (tot + 1) >> 1; make_heap(Heap, Heap + m); for(int i = 0; i < m; i++) pos[Heap[i].b] = i; read(Q); while (Q--) { scanf("%s", op1), op = op1[0]; if (op == 'A') { if(!white) puts("They have disappeared."); else if(white == 1) puts("0"); else printf("%d\n", max(Heap[0].a, 0)); } else { read(x); color[x] == 0 ? white-- : white++; color[x] ^= 1; for(auto t : idx[x]) { int id = t.a, dist = t.b; if(color[x] == 0) h[id].emplace(data(dist, x)); while(~h[id].top().b && color[h[id].top().b] == 1) h[id].pop(); Heap[pos[id >> 1]].a = h[id].top().a + w[id] + h[id ^ 1].top().a; down(pos[id >> 1]); up(pos[id >> 1]); } } } return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注