ABC460F 题解

赛时看到 F 马上就想到点分树，只剩十分多钟口胡了一下就跑了。

赛后看题解发现全是线段树分治做的，去原题 P2056 学习了一下点分树做法。发现赛时的口胡离正解还差得远。

首先做一个重链剖分，进而可以以 的时间求出任意两点间的距离。

把点分树建出来，对于节点 ，只要考虑在 子树内、经过 的路径 。也就是说， 在 的两个不同的孩子的子树中，或者 有一个是 。这些路径的最大长度记为 ，那么全局答案就是 。

具体如何求出 ？

下面记点分树上 的父亲为 。

路径是由两段以 为端点的路径拼起来的，所以我们只要找到这些路径长度最大值与次大值。 将 子树内所有点到 的距离存在集合 中（这个集合肯定要用数据结构维护啦，具体后面会讲）。然后对于 再维护一个集合 （这个也要用数据结构维护，具体后面会讲），里面有每个 在点分树上的孩子子树内所有黑点到 距离的最大值。当然，如果 也是黑点，还要在集合中加入它到它自己的距离，也就是 。那么 就是 中的最大值与次大值之和。我们还要统计全局答案，开一个集合 存所有的 。

最开始的 可以暴力直接求出来，因为点分树树高为 ，一个点只会加入到它祖先的 中，而它的祖先只有 个。对于所有点 ，将它的 的最大值挑出来，扔到 中，这样我们初始化就完成了。

代码长这样。

fo(u , 1 , n){ // for(int u = 1 ; u <= n ; u++) 的意思 int cur = u; while(up[cur]){ dis_to_up[cur].push(dis(up[cur] , u)); cur = up[cur]; } } fo(u , 1 , n){ max_in_every_son[u].push(0); // 别忘了它自己 if(up[u] != 0) max_in_every_son[up[u]].push(dis_to_up[u].query1()); // query1 是查询最大值的函数 } fo(u , 1 , n){ all.push(max_in_every_son[u].query12()); // query12 是查询最大值与次大值之和的函数 }

现在我们考虑修改一个点的颜色会改变什么。显然它的所有祖先的 与 都要修改。具体的，设 为 的某一个祖先，那么将 改为白点 / 黑点就是在 中删除 / 加入 。然后 的最大值要贡献给 ，那么要在 中删去原来的最大值，再加入 新的最大值。这样 也改变了，在 中删除旧的 ，加入新的。这样修改操作也完成啦。

代码长这样。

fo(u , 1 , n) black[u] = 1; cin >> q; while(q--){ int u; cin >> u; if(black[u] == 1){ black[u] = 0; int pre1 = max_in_every_son[u].query12(); // 别忘了它自己 max_in_every_son[u].remove(0); int now1 = max_in_every_son[u].query12(); all.remove(pre1) , all.push(now1); int cur = u; while(up[cur]){ int pre = dis_to_up[cur].query1(); dis_to_up[cur].remove(dis(up[cur] , u)); int now = dis_to_up[cur].query1(); int pre1 = max_in_every_son[up[cur]].query12(); max_in_every_son[up[cur]].remove(pre); max_in_every_son[up[cur]].push(now); int now1 = max_in_every_son[up[cur]].query12(); all.remove(pre1) , all.push(now1); cur = up[cur]; } } else{ black[u] = 1; int pre1 = max_in_every_son[u].query12(); max_in_every_son[u].push(0); int now1 = max_in_every_son[u].query12(); all.remove(pre1) , all.push(now1); int cur = u; while(up[cur]){ int pre = dis_to_up[cur].query1(); dis_to_up[cur].push(dis(up[cur] , u)); int now = dis_to_up[cur].query1(); int pre1 = max_in_every_son[up[cur]].query12(); max_in_every_son[up[cur]].remove(pre); max_in_every_son[up[cur]].push(now); int now1 = max_in_every_son[up[cur]].query12(); all.remove(pre1) , all.push(now1); cur = up[cur]; } } cout << all.query1() << "\n"; }

看着很长，但黑变白，白变黑只有remove与push的区别，其他代码是重复的。

接着考虑 ， 与 三个集合如何维护。它们要实现的功能有：

• 加入一个数

• 删除一个数

• 查询最大值

• 查询最大值与次大值之和

这个可以用两个优先队列实现，集合中的数存在一个队列 中，删除的数暂时存在另一个队列 中。取出最大值时，如果它也是 中的最大值就两个都弹掉。

struct Natho_nA{ priority_queue<int> a , del; void push(int x){ a.push(x); } void remove(int x){ del.push(x); } int query1(){ while(a.size() and del.size() and a.top() == del.top()){ a.pop() , del.pop(); } if(a.size()) return a.top(); else return -inf; } int query12(){ int first = query1(); if(first == -inf) return -inf; a.pop(); int second = query1(); a.push(first); return first + second; } }; Natho_nA dis_to_up[maxn + 5] , max_in_every_son[maxn + 5] , all;

至此所有都完成啦。

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> #define mp make_pair #define fo(i , x , y) for(int i = x ; i <= y ; i++) #define go(i , x , y) for(int i = x ; i >= y ; i--) // #define local #ifdef local #define debug(x) cerr << #x" : " << x << ", " #define debugn(x) cerr << #x" : " << x << "\n" #define debugarr(a , n); cerr << #a" : \n"; fo(i , 1 , n) cerr << a[i] << " "; cerr << "\n"; #else #define debug(x) "n-buna bless me." #define debugn(x) "wowaka bless me." #define debugarr(a , n) "Nayutan bless me." #endif using namespace std; const int maxn = 100000; const int inf = maxn * 100; int n , q , black[maxn + 5]; vector<int> e[maxn + 5]; // 重链剖分 int fa[maxn + 5] , siz[maxn + 5] , dep[maxn + 5] , top[maxn + 5] , son[maxn + 5]; void dfs1(int u , int f){ fa[u] = f; dep[u] = dep[f] + 1; siz[u] = 1; for(int v : e[u]){ if(v == f) continue; dfs1(v , u); siz[u] += siz[v]; if(siz[son[u]] < siz[v]) son[u] = v; } } void dfs2(int u , int f , int tp){ top[u] = tp; if(son[u]) dfs2(son[u] , u , tp); for(int v : e[u]){ if(v == f or v == son[u]) continue; dfs2(v , u , v); } } int lca(int u , int v){ while(top[u] != top[v]){ if(dep[top[u]] < dep[top[v]]) swap(u , v); u = fa[top[u]]; } if(dep[u] > dep[v]) swap(u , v); return u; } int dis(int u , int v){ int f = lca(u , v); return dep[u] - dep[f] + dep[v] - dep[f]; } // 建点分树 int up[maxn + 5]; bool vis[maxn + 5]; int get_root(int u , int sum , int fa){ int ans = -1; siz[u] = 1; // 这里的 siz 数组用的是重链剖分的，初始化过不用担心 bool flag = true; for(int v : e[u]){ if(v == fa) continue; if(vis[v]) continue; int res = get_root(v , sum , u); if(res != -1) ans = res; if(siz[v] * 2 > sum) flag = false; siz[u] += siz[v]; } if(ans != -1) return ans; if(flag and (sum - siz[u]) * 2 <= sum) return u; return -1; } void solve(int rt , int sum){ vis[rt] = true; for(int v : e[rt]){ if(vis[v]) continue; int sumv = (siz[v] < siz[rt] ? siz[v] : sum - siz[rt]); int w = get_root(v , sumv , 0); up[w] = rt; solve(w , sumv); } } struct Natho_nA{ priority_queue<int> a , del; void push(int x){ a.push(x); } void remove(int x){ del.push(x); } int query1(){ while(a.size() and del.size() and a.top() == del.top()){ a.pop() , del.pop(); } if(a.size()) return a.top(); else return -inf; } int query12(){ int first = query1(); if(first == -inf) return -inf; a.pop(); int second = query1(); a.push(first); return first + second; } }; Natho_nA dis_to_up[maxn + 5] , max_in_every_son[maxn + 5] , all; int main(){ ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0); // freopen(".in" , "r" , stdin); // freopen(".out" , "w" , stdout); cin >> n; fo(i , 1 , n - 1){ int u , v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dfs1(1 , 0); dfs2(1 , 0 , 1); solve(get_root(1 , n , 0) , n); fo(u , 1 , n){ int cur = u; while(up[cur]){ dis_to_up[cur].push(dis(up[cur] , u)); cur = up[cur]; } } fo(u , 1 , n){ max_in_every_son[u].push(0); if(up[u] != 0) max_in_every_son[up[u]].push(dis_to_up[u].query1()); } fo(u , 1 , n){ all.push(max_in_every_son[u].query12()); } fo(u , 1 , n) black[u] = 1; cin >> q; while(q--){ int u;