AT_abc460_f 解题报告

极客资料网推荐AT_abc460_f 解题报告这篇文章给大家，欢迎收藏极客资料网享受知识的乐趣

1min 啊，维护直径吗？

2min 对图进行改变，直径肯定只会有细微的变化，怎么变呢？

10min 我想不到，看题解（那我很糖了，都想到第二步了）。

重要结论：取点集 \(S\) 的任意直径 \((u,v)\) 和 \(T\) 的任意直径 \((x,y)\)，\(S \cup T\) 的直径如果比原来更长，那么一定是 \((u,x)\)，\((u,y)\)，\((v,x)\)，\((v,y)\) 中的一个。

然后加点就简单了，每次随便选一条直径，用两个端点和新加的点更新答案。

如果要删点的话，根据刚刚得出的结论，注意到这玩意其实是可以合并的，为什么不试试线段树呢？具体地，代表 \([l,r]\) 的节点维护 \([l,r]\) 中黑点的直径，使用 LCA 快速找距离，然后就做完了。

总结一下直觉：注意到两个子树的直径可以快速合并，然后又是区间查/单点改，就不难想到线段树了。

这个东西让我想到了 road 的 trick，对于一个边集 \(S\) 的最小生成树边集 \(D\)，\(S \cup T\) 的最小生成树不可能包含 \(\complement_S D\) 中的边。共同点就是利用“新的最优解只和两个部分的最优解有关”这个性质。

// Code by GENX.
// 2026-05-31
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
int n;
vector<int> g[N];

int fa[N][23], dep[N];
void dfs(int u, int pre){
	dep[u] = dep[pre] + 1;
	fa[u][0] = pre;
	for(int i = 1; i <= 20; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(int v: g[u]) if(v != pre) dfs(v, u);
}
int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 20; i >= 0; i --) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
	if(x == y) return x;
	for(int i = 20; i >= 0; i --) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
int dis(int x, int y){
	if(x == -1 || y == -1) return -1;
	return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

tuple<int, int, int> gen(int x, int y){
	return {dis(x, y), x, y};
}
tuple<int, int, int> operator + (tuple<int, int, int> a, tuple<int, int, int> b){
	tuple<int, int, int> res = max(a, b);
	auto [disa, ua, va] = a;
	auto [disb, ub, vb] = b;
	res = max({res, gen(ua, ub), gen(ua, vb), gen(va, ub), gen(va,vb)});
	return res;
}
struct Misaka{
	#define ls (x << 1)
	#define rs ((x << 1) | 1)
	#define mid ((l + r) >> 1)
	tuple<int, int, int> v[N << 2];
	void build(int x, int l, int r){
		if(l == r) return v[x] = gen(l, l), void();
		build(ls, l, mid), build(rs, mid + 1, r);
		v[x] = v[ls] + v[rs];
	}
	int toggle(int x, int l, int r, int k){
		if(l == r){
			if(get<0>(v[x]) == -1) v[x] = gen(l, l);
			else v[x] = {-1, -1, -1};
			return get<0>(v[x]);
		}
		if(k <= mid) toggle(ls, l, mid, k);
		else toggle(rs, mid + 1, r, k);
		v[x] = v[ls] + v[rs];
		return get<0>(v[x]);
	}
};
Misaka Mikoto;

void init(){
	cin >> n;
	for(int i = 1; i <= n; i ++) g[i].clear();
	for(int i = 1; i < n; i ++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0), Mikoto.build(1, 1, n);
}

int col[N];
void solve(){
	int x; cin >> x;
	cout << Mikoto.toggle(1, 1, n, x) << "\n";
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	init();
	int q; cin >> q;
	while(q --) solve();
	return 0;
}

文章来源:https://www.cnblogs.com/GE9X/p/20239358
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！