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';
}
标签:fax,fay,Infinity,个点,Tree,ICPC,while,编号,节点
From: https://www.cnblogs.com/DM11/p/16768093.html