自助设计网站,wordpress 站点换域名,大数据营销实训心得体会,怎么把网站的标题做的炫酷树上倍增可以比较容易求得i节点的第k个父亲#xff0c;我们定义一个二维数组fa[i][j]代表节点i的第2^j个父亲#xff0c;关于有什么用我们等会再说#xff0c;现在先学会怎么去求这个fa数组 我们可以通过从根节点开始一遍dfs求得所有fa数组#xff0c;首先我们发现fa数组有…树上倍增可以比较容易求得i节点的第k个父亲我们定义一个二维数组fa[i][j]代表节点i的第2^j个父亲关于有什么用我们等会再说现在先学会怎么去求这个fa数组 我们可以通过从根节点开始一遍dfs求得所有fa数组首先我们发现fa数组有这样一个特性fa[i][j] fa[ fa[i][j-1] ][j-1]什么意思呢就是说节点i的第2^j个父亲就是i的第2^(j-1)个父亲的第2^(j-1)个父亲这看起来似乎是一句显然成立的废话但我们可以通过这个特性以O(nlogn)的复杂度内求fa数组。 我们知道dfs是从根开始一步一步往下走的这就说明除了根节点每个节点当它被dfs到的时候它的所有父亲肯定都已经被dfs过了这样通过刚才的关系就可以由i的第2^(j-1)个父亲求fa[i][j]了我们需要处理的只是i的第2^j个父亲有可能不存在罢了。我们初始化fa数组为0然后从根开始dfs。若有n个节点则显然一个节点最多只可能往前找2^log(n)个父亲 void dfs(int x)
{ for(int i1;ilogn;i) //logn代表log(n)if(fa[x][i-1]) //在dfs(x)之前x的父亲们的fa数组都已经计算过了fa[x][i]fa[fa[x][i-1]][i-1]; else break; //x的第2^j个父亲可能不存在for(/*每一个与x相连的节点i*/) if(i!fa[x][0]) //如果i是x的儿子{ fa[i][0]x; //记录儿子的第一个父亲是x dep[i]dep[x]1; //深度 dfs(i); }
} 求出fa数组后有什么用呢其实我们可以轻易的在O(logk)内求出i的第k个父亲根据数组定义看起来我们只能求i的第248...2^j次方个父亲实际上我们可以求出i的第任意个父亲 我们有这样一个事实任何一个数都可以写成多个2的x次方的和实际上这就是2进制转10进制的过程比如10的二进制表示为1010它的左数第2位和第4位上是1所以2^(2-1)2^(4-1) 2^1 2^3 10。这个思想很有用需要记住 所以对于任意一个数k只要我们把它写成若干个2的次方形式的数的和就可以利用fa数组了。 另外我们代码中还有个技巧(1i)k表示k的二进制表示中左数第(i-1)位上是否为1 经过上面知识我们可以写出求i的第k个父亲的代码 int father(int i,int k)
{ for(int x0;xint(log2(k));x) if((1x)k) ifa[i][x]; return i;
} 转载于:https://www.cnblogs.com/chaoswr/p/8489224.html
