- QTREE 4: 切换点的颜色(黑白)/询问两白点间的最远距离
- QTREE 5: 切换点的颜色(黑白)/询问某点离白点的最近距离
QTREE 4
很经典的题~ [bzoj 1095] [ZJOI2007]Hide 捉迷藏 的带边权版本. 先前在Po姐的博客里学到了神奇的动态树分治, 但是没有写, 觉得会很麻烦. 事实上, 把思路理清, 无视掉所有常数上的优化, 写起来不是很困难.
如果只有一次询问, 点分治可以这样做 (其实DP就可以啦~): 把路径分成过重心的和不过重心的, 前者用从重心向下走到达某白点的最长和次长距离 (不能在同一棵子树中) 更新, 后者递归处理.
如果带修改呢? 树的结构是不变的, 每次递归的重心可以预处理出来, 并注意到把上一层的重心和本层的重心连起来, 也形成了一棵n个结点深度O(lg n)的树 (不妨称之为递归树). 每个点到其递归树上祖先的距离也可以预处理出来. 修改简化为从一些重心在原树上的某棵子树添加或删除一个距离. 它可能会影响到该重心的最长+次长 - 取决于该子树向下的最大长度是否变化. 这个重心的最长+次长变化, 又可能会影响到答案. 于是, 设计出这样一套方案: - 每个点开一个大根堆len, 维护递归树上以该点为根的子树中, 所有白点到该点在递归树上父亲的距离 (距离是原树上的) - 每个点再开一个大根堆local, 维护递归树上该点所有儿子的len的堆顶的值; 如果该点是白点, 则加入0 - 一个全局的堆global, 维护每个local中的最大值+次大值
自己思考的时候, 没有发现重心也形成了树的结构, 也没想到开一个全局的堆以支持删除.
实现上的细节: - 堆需要支持删除特定元素, 不能直接上std::priority_queue. 在Po姐等神犇的题解中看到一个不错的方案: 用两个优先队列A,B, 添加元素push到A中, 删除元素push到B中, 查询时比较两者堆顶进行抵消. 这样不用手写, 效率摊还下来仍是修改O(lg n), 查询O(1). 有一个小遗憾, 即查询次大值是O(lg n)的. - 堆适时地返回inf以简化讨论.
const int N = 1e5, inf = (1<<30)-1;
template<typename T>
struct Heap {
priority_queue<T> A, B;
int size()
{
return A.size() - B.size();
}
void push(const T& v)
{
A.push(v);
}
void erase(const T& v)
{
B.push(v);
}
void update()
{
while (!B.empty() && A.top() == B.top()) {
A.pop();
B.pop();
}
}
T top()
{
if (!size()) return -inf;
update();
return A.top();
}
T two()
{
if (size() < 2) return 0;
T x = top();
A.pop();
T y = top();
push(x);
return x + y;
}
void pop()
{
update();
A.pop();
}
};
struct Edge {
int to, w, nxt;
} E[2*N];
int root, ptr = 1, adj[N+1], sz[N+1], fa[N+1];
Heap<int> global, local[N+1], len[N+1];
vector<int> dis[N+1];
bool g[N+1], color[N+1];
inline void add(int x, int y, int w)
{
E[ptr] = (Edge){y, w, adj[x]};
adj[x] = ptr++;
}
int get_centroid(int u, int p, int n)
{
int x = 0, mx = 0;
sz[u] = 1;
for (int i = adj[u]; i; i = E[i].nxt) {
int v = E[i].to;
if (g[v] || v == p) continue;
int y = get_centroid(v, u, n);
if (!x) x = y;
sz[u] += sz[v];
mx = max(mx, sz[v]);
}
return x ? x : (max(mx, n-sz[u]) <= n/2 ? u : 0);
}
void get_dist(int u, int w, int p, Heap<int>& h)
{
dis[u].push_back(w);
h.push(w);
for (int i = adj[u]; i; i = E[i].nxt) {
int v = E[i].to;
if (!g[v] && v != p)
get_dist(v, w + E[i].w, u, h);
}
}
void decompose(int x, int n)
{
g[x] = true;
for (int i = adj[x]; i; i = E[i].nxt) {
int y = E[i].to;
if (g[y]) continue;
int s = sz[y]<sz[x] ? sz[y] : n-sz[x], z = get_centroid(y, x, s);
fa[z] = x;
get_dist(y, E[i].w, x, len[z]);
local[x].push(len[z].top());
decompose(z, s);
}
local[x].push(0);
global.push(local[x].two());
}
void modify(int x, bool t)
{
for (int y = x; y; y = fa[y])
global.erase(local[y].two());
for (int y = x; y != root; y = fa[y])
local[fa[y]].erase(len[y].top());
if (t) local[x].push(0);
else local[x].erase(0);
vector<int>::reverse_iterator d = dis[x].rbegin();
for (int y = x; y != root; y = fa[y]) {
if (t) len[y].push(*d++);
else len[y].erase(*d++);
local[fa[y]].push(len[y].top());
global.push(local[y].two());
}
global.push(local[root].two());
}
int main()
{
int n;
scanf("%d", &n);
int cnt = n;
rep (i, 0, n-1) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
root = get_centroid(1, 0, n);
decompose(root, n);
global.push(0);
int q;
scanf("%d", &q);
while (q--) {
char o;
int x;
scanf(" %c", &o);
if (o == 'A') {
if (cnt)
printf("%d\n", global.top());
else
puts("They have disappeared.");
} else {
scanf("%d", &x);
modify(x, color[x]);
cnt += color[x] ? 1 : -1;
color[x] ^= 1;
}
}
return 0;
}QTREE 5
可以和上题采用类似的策略.
全局的堆不需要了. 查询时沿着递归树上的边向上走, 查找兄弟结点len堆顶的最小值 (本题问的是最小距离).
const int inf = (1<<30)-1, N = 1e5;
template<typename T>
struct Heap {
priority_queue<T, vector<T>, greater<T> > A, B;
void push(const T& v)
{
A.push(v);
}
void erase(const T& v)
{
B.push(v);
}
void update()
{
while (!B.empty() && A.top() == B.top()) {
A.pop();
B.pop();
}
}
int size()
{
return A.size() - B.size();
}
T top()
{
if (!size()) return inf;
update();
return A.top();
}
T top_ignore(const T& v)
{
T x = top();
if (x != v || x == inf) return x;
A.pop();
T y = top();
push(x);
return y;
}
};
struct Edge {
int to, nxt;
} E[2*N];
typedef vector<int>::reverse_iterator rit;
int ptr = 1, root, adj[N+1], fa[N+1], sz[N+1];
bool g[N+1], color[N+1];
Heap<int> len[N+1], sub[N+1];
vector<int> dis[N+1];
inline void add(int x, int y)
{
E[ptr] = (Edge){y, adj[x]};
adj[x] = ptr++;
}
int get_centroid(int u, int p, int n)
{
int x = 0, mx = 0;
sz[u] = 1;
for (int i = adj[u]; i; i = E[i].nxt) {
int v = E[i].to;
if (g[v] || v == p) continue;
int y = get_centroid(v, u, n);
if (!x) x = y;
sz[u] += sz[v];
mx = max(mx, sz[v]);
}
return x ? x : (max(mx, n-sz[u]) <= n/2 ? u : 0);
}
void get_dist(int u, int p, int d)
{
dis[u].push_back(d);
for (int i = adj[u]; i; i = E[i].nxt) {
int v = E[i].to;
if (!g[v] && v != p)
get_dist(v, u, d+1);
}
}
void decompose(int x, int n)
{
g[x] = true;
for (int i = adj[x]; i; i = E[i].nxt) {
int y = E[i].to;
if (g[y]) continue;
int s = sz[y]<sz[x] ? sz[y] : n-sz[x], z = get_centroid(y, x, s);
get_dist(y, x, 1);
sub[x].push(inf);
fa[z] = x;
decompose(z, s);
}
}
void modify(int x, bool t)
{
if (t) sub[x].push(0);
else sub[x].erase(0);
rit d = dis[x].rbegin();
for (int y = x; y != root; y = fa[y]) {
sub[fa[y]].erase(len[y].top());
if (t) len[y].push(*d++);
else len[y].erase(*d++);
sub[fa[y]].push(len[y].top());
}
}
int query(int x)
{
int ans = sub[x].top();
rit d = dis[x].rbegin();
for (int y = x; y != root; y = fa[y])
ans = min(ans, sub[fa[y]].top_ignore(len[y].top()) + *d++);
return ans;
}
int main()
{
int n;
scanf("%d", &n);
int cnt = 0;
rep (i, 0, n-1) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
root = get_centroid(1, 0, n);
decompose(root, n);
int q;
scanf("%d", &q);
while (q--) {
int o, x;
scanf("%d%d", &o, &x);
if (o) {
printf("%d\n", cnt ? query(x) : -1);
} else {
modify(x, color[x] ^= 1);
cnt += color[x] ? 1 : -1;
}
}
return 0;
}