命題
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)