2022 ICPC网络赛（二） F Infinity Tree

题意：

​ 现在给出一个树，对于这棵树，一开始有一个根节点1，每秒之后，每个节点会长出k个节点。节点的最大编号为\(1e18\)。现在给出任意两个节点编号a, b，还有每秒生成的节点个数k。请问节点a，b的最近公共祖先的编号是多少。

思路：

​ 题目已经指出了LCA。由于层数最多是\(log2(1e18)\)大概不到100层，所以我们可以直接采取最朴素的LCA思想，也就是取深度大的点向上跳。从1开始不断*(k+1)就可以得到x和y的父节点，那我们对比x和y的编号大小，谁编号大谁就深，向上跳一个，然后再暴力更新其父亲位置，直到跳到x等于y为止。那么我们还需要通过规律来推出，如何从一个节点的编号得到其父亲节点的编号。

​ 我们可以设k为2，手推可以发现，第一秒有1个点，第二秒有3个点，第三秒有9个点。那么第四秒将会有27个点，且在第四秒出生的点编号为[10 - 27]，通过题意可以知道，10 11是由点1生成的，12 13是由点2生成的，以此类推。我们可以重新编号一下，10是第四秒的出生的1号点，11是第四秒出生的二号点，可以知道在第四秒出生的前k个点的父亲都是1，在第四秒出生的[k + 1 - 2 * k]个点的父亲都是2。得出规律，将(当前点编号 - 上一秒出生的点的总数) / k（上取整）即可O1得到父亲节点的编号。

实现：

​ 可能会乘爆，那就开一个__int128来存一下就好。

ll ceil(ll x, ll y)	{return (x + y - 1) / y;} //上取整

void solve()
{
	ll k, x, y;
	cin >> k >> x >> y;
	__int128 fax = 1, fay = 1;
	while(fax < x)
		fax *= (k + 1);
	fax /= (k + 1);
	while(fay < y)
		fay *= (k + 1);
	fay /= (k + 1);
	
	while(x != y)
	{
		if(x > y)
		{
			x = ceil(x - fax, k); 
			
			fax = 1; //重新找父节点
			while(fax < x)
				fax *= (k + 1);
			fax /= (k + 1);
		}
		else
		{
			y = ceil(y - fay, k);

			fay = 1; //重新找父节点
			while(fay < y)
				fay *= (k + 1);
			fay /= (k + 1);
		}
	}
	cout << x << '\n';
}