赛时看到 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_queueint 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;至此所有都完成啦。#includecmath #includecstdio #includecstring #includeiostream #includealgorithm #includequeue #includevector #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]; vectorint 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_queueint 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;