SPOJ Query On A Tree IV 题解
一个边分治套线段树套堆的题目
比较难写但是有不小的启发
思路来源和代码都抄自 [SPOJ-QTREE4]QUERY ON A TREE IV 题解 | KSKUN' s Blog
简要题意
给定一个 \(n\) 个点的带边权树， 点的编号为 \(1\sim n\)， 初始树上所有节点都是白色的， 要求维护两个操作：
- \(\rm {C\ a}\) 反转 \(a\) 节点的颜色（白色变成黑色或者黑色变成白色）
- \(\rm A\) 查询树上最远的两个白点的距离
特别的，进行 \(\rm A\) 操作时如果树上没有白点输出 They have disappeared.
\(N\le 10^5, Q\le 10^5, -10^3\le c\le 10^3\)
做法
在线版：
树上的问题太难了，先把这个问题丢到一个序列里面做看看有没有什么启发性的做法
问题变成给你一个 \(01\) 序列，询问变成每次反转一个数，以及查询两个距离最远的 \(1\) 相隔的距离
这个问题如果是静态的（忽略操作 \(1\)）就是双指针扫一下两端第一个 \(1\) 的位置就可以了
但是这个做法没什么前途，因为在带修的情况下每次都要重新确定答案（这相当于维护序列的前缀和和后缀和，每次修改要变动很多东西），而且放到树上不太现实。
考虑一种过中点的分治，每次取序列的中点，把序列分为左半和右半两个子序列，维护左半子序列和右半子序列所有为 \(1\) 的点到中点的距离，左半和右半各取一个 \(\max\) 合起来就是横跨中点的答案，然后递归左子序列和右子序列，那么当前序列的答案就是 \(\max(self\_max,left\_max,right\_max)\)
考虑这个分治的原因是一个点至多属于 \(\log\) 个子序列，修改是 \(\log\) 的
这个种分治带修很好做，这东西长得就像线段树的形式自然可以像线段树那样维护
至于带修，每个节点维护左子序列所有点到中点的距离的一个大根堆，右子序列所有点到中点距离的一个大根堆，把堆顶所有黑色节点弹出，取两个堆顶即可，修改的时候，白改黑就是把点置为黑色，更新答案，黑改白就是把点置为白色，把点重新插进堆里面去，更新答案
好，序列上做完了考虑把这东西塞到树上去
原来序列过中点分治现在显然就是边分治（因为每次要把树分成两半，多了不好合并答案）
对分出来的两个子树分别开个堆维护最大值，然后接下来对子树再进行分治，和上面完全是一模一样的道理
注意有两个问题就是树上跟序列上不太一样，给一个点不好确定它在每一层中心边的左侧还是右侧，这个可以对每个点开一个长度为 \(\log\) 的数组，然后维护它每一层属于哪条中心边的哪一侧
而且也不好直接做线段树的区间编号，需要用类似动态开点的方式维护编号，更新很难递归，直接自底向上更新就好了
具体可以看一下示例代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <vector>
typedef long long ll;
const int N = 1e5 + 10, M = 2e5 + 10, inf = 0x7f7f7f7f;
int h[N], e[M], ne[M], w[M], idx;
int n;
void add(int x, int y, int c){
e[idx] = y, ne[idx] = h[x], w[idx] = c, h[x] = idx++;
}
namespace new_tree{
int h[N << 1], e[M << 1], ne[M << 1], w[M << 1], idx;
int NodeNum;
//节点的颜色, false为白, true为黑
bool color[N << 1];
int WhiteNum;
void add(int x, int y, int c){
e[idx] = y, ne[idx] = h[x], w[idx] = c, h[x] = idx++;
}
//重建树
void rebuild(int u, int fa){
int ff = 0;
for(int i = ::h[u]; ~i; i = ::ne[i]){
int v = ::e[i];
if(v == fa)
continue;
if(!ff){
add(u, v, ::w[i]);
add(v, u, ::w[i]);
ff = u;
}
else{
int tmp = ++NodeNum;
color[tmp] = 1;
add(tmp, ff, 0);
add(ff, tmp, 0);
add(tmp, v, ::w[i]);
add(v, tmp, ::w[i]);
ff = tmp;
}
rebuild(v, u);
}
}
/****************树上分治部分****************/
bool vis[M << 1];
int siz[N << 1];
int MinMax;
int core;
/********************算中心边*********************/
void getsiz(int u, int fa){
siz[u] = 1;
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(vis[i] || v == fa)
continue;
getsiz(v, u);
siz[u] += siz[v];
}
}
void getcore(int u, int tot, int fa){
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(v == fa || vis[i])
continue;
int Maxn = std::max(siz[v], tot - siz[v]);
if(Maxn < MinMax){
MinMax = Maxn;
core = i;
}
getcore(v, tot, u);
}
}
/******************分治结构需要维护的信息**************/
//树上边分治每次把树分成两个部分
//对每个结构开一个优先队列维护双端最大值
//具体来说, 结构类似于线段树
struct dis_info{
int u, d;
bool operator < (const dis_info &b) const {
return d < b.d;
}
};
std::priority_queue<dis_info> q[N << 1][2];
int cnt;
struct Node{
//div 是一个分治结构的编号
int div, side, dis;
};
//对于每个节点, 维护每层它属于哪个分治结构（所属中心边编号）, 方便更新
//类似于线段树, 维护每层它属于哪个区间
//log层, 空间n log n
std::vector<Node> node[N << 1];
struct Seg_Node{
int ls, rs, core_w, maxn;
}tr[N << 1];
/********************更新分治结构信息******************/
//p是分治结构编号
void upd(int p){
while(!q[p][0].empty() && color[q[p][0].top().u])
q[p][0].pop();
while(!q[p][1].empty() && color[q[p][1].top().u])
q[p][1].pop();
//如果左侧或者右侧没有白点
if(q[p][0].empty() || q[p][1].empty())
tr[p].maxn = 0;
else
tr[p].maxn = q[p][0].top().d + q[p][1].top().d + tr[p].core_w;
//和左右子树取max
if(tr[p].ls) tr[p].maxn = std::max(tr[p].maxn, tr[tr[p].ls].maxn);
if(tr[p].rs) tr[p].maxn = std::max(tr[p].maxn, tr[tr[p].rs].maxn);
}
void set_white(int u){
//自底向上
for(int i = node[u].size() - 1; i >= 0; i--){
Node d = node[u][i];
//把节点重新入队
q[d.div][d.side].push({u, d.dis});
upd(d.div);
}
}
void set_black(int u){
//自底向上
for(int i = node[u].size() - 1; i >= 0; i--){
Node d = node[u][i];
upd(d.div);
}
}
/**********************裁剪分治结构********************/
//计算结构内信息
//t是结构编号, side是在结构哪一侧
void calc_dis(int u, int fa, int d, int t, int side){
//白点需要计算距离
if(!color[u]){
q[t][side].push({u, d});
node[u].push_back({t, side, d});
}
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(v == fa || vis[i])
continue;
calc_dis(v, u, d + w[i], t, side);
}
}
int dfs(int x){
MinMax = NodeNum;
getsiz(x, 0);
core = -1;
getcore(x, siz[x], 0);
//没有边可以找了
if(core == -1) return 0;
int from = e[core], to = e[core ^ 1];
//删掉这一条边
vis[core] = vis[core ^ 1] = true;
//新结构的编号
int t = ++cnt;
tr[t].core_w = w[core];
calc_dis(from, 0, 0, t, 0);
calc_dis(to, 0, 0, t, 1);
//构建分治结构
tr[t].ls = dfs(from);
tr[t].rs = dfs(to);
upd(t);
return t;
}
/****************主体框架部分****************/
void solve(){
WhiteNum = ::n;
memset(h, -1, sizeof h);
NodeNum = ::n;
rebuild(1, -1);
dfs(1);
int query;
scanf("%d", &query);
for(int i = 1; i <= query; i++){
char op[2];
scanf("%s", op);
if(op[0] == 'A'){
if(!WhiteNum){
puts("They have disappeared.");
}
else if(WhiteNum == 1){
puts("0");
}
else{
printf("%d\n", tr[1].maxn);
}
}
else{
int u;
scanf("%d", &u);
color[u] ^= 1;
if(color[u]){
set_black(u);
WhiteNum--;
}
else{
set_white(u);
WhiteNum++;
}
}
}
}
}
int main(){
memset(h, -1, sizeof h);
scanf("%d", &n);
for(int i = 1; i < n; i++){
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
add(x, y, c), add(y, x, c);
}
new_tree::solve();
return 0;
}
这种比较大型的数据结构代码一定要想清楚实现细节再写，搞清楚在干什么再动笔
否则会调很久很久
离线版
上面的在线做法好像不太聪明啊
上面的做法相当于每一次询问都对整个树重新做了一次边分治，只是注意到了每次至多修改 \(\log\) 层的信息所以可以用线段树做到比较快的修改而已
从点分治板子里我们意识到一件事情
树上分治是可以 \(Q\) 个询问一起做的，因为每次分治得到的两侧信息不会有太大的变化，没必要重新算一遍，可以重复利用
所以其实可以把线段树砍掉，不需要每次维护修改对全局答案的影响，直接 \(Q\) 个询问一起做，直接边分治，每次两侧的答案用一个大根堆维护，然后依次执行询问，还是类似，白变黑直接变，黑变白先把点插进堆里再变，然后每次询问把堆顶所有黑点弹出然后再取堆顶就行了
使用一些配对堆或者斐波那契堆科技可以把复杂度再干掉一个 $\log $（堆插入）， 时间复杂度是 \((n+Q)\log n\)， 空间复杂度如果及时析构可以做到 \(O(n)\)，大概可以卡一个最优解了
代码没写，只写了在线版的
标签：core,int,题解,分治,SPOJ,序列,Query,include,side From： https://www.cnblogs.com/lostintianyi/p/17167486.html