CF1617E Christmas Chocolates

「2023zimpha」树的直径练习题

题目传送门

有 $n$ 个互不相同的数 $a_1,a_2,\dots,a_n$。

每次操作，选定一个数 $a_i$ 和一个非负整数 $k$ 满足 $2^k \le a_i$，然后将 $a_i$ 替换为 $2^k-a_i$。

定义 $dis(a_i,a_j)$ 为最少需要的操作次数，使得 $a_i=a_j$（每次操作只能对 $a_i$ 使用）。

选出一对 $a_i,a_j$ 使 $dis(a_i,a_j)$ 最大。

$n \le 2\cdot 10^5, a_i \le 10^9$

在可以通过一次操作互相转化的两个数之间连一条边。

可以发现，这样建出来的图一定是一棵树（每个数都只能转化到唯一一个比自己小的数）。这棵树的根节点为 0。

原问题转化为：求在树上距离最大的一组 $a_i,a_j$。

用树的直径求法，先找到距离 $a_1$ 最远的点 $a_u$，再找到距离 $a_u$ 最远的点 $a_v$。那么 $a_u,a_v$​ 即为答案。

因为每次操作大概是除以二，所以点的深度是 log 级别。求距离可以用暴力跳，单次复杂度 log。

总复杂度 $O(n \log n)$。

Code

int n, a[N];
unordered_map<int, int> num;
int cnt, fa[32 * N], dep[32 * N], zero;
queue<int> q;
int dis(int x, int y) {
	int d = 0;
	while(x != y) {
		if(dep[x] >= dep[y]) x = fa[x];
		else y = fa[y];
		d++;
	}
	return d;
}
int u = 1, v = 1;
set<int> s;
void solve() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	    num[a[i]] = i + 1;
	    q.push(a[i]);
	}
	cnt = n;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		s.insert(x);
		if(!x) continue;
		int y = 1;
		while(y < x) y *= 2;
		y = y - x;
		if(!num[y]) {
			num[y] = ++cnt;
			q.push(y);
		}
		fa[num[x]] = num[y];
	}
	for(int i: s) if(i) dep[num[i]] = dep[fa[num[i]]] + 1;
	repp(i, n) if(dis(1, i) > dis(1, u)) u = i;
	repp(i, n) if(dis(u, i) > dis(u, v)) v = i;
	if(u > v) swap(u, v);
	cout << u << ' ' << v << ' ' << dis(u, v);
}