树链剖分

关于长链剖分中指针的理解

与指针有关的变量：$\ast dp[N],tmp[N]$,$\ast pos$

---

pos=tmp;//将pos指向tmp空间
dp[1]=pos, pos+=height[1];
   //改变后pos加上dp[1]所需的长度，防止内存冲突

可以把 $*dp[1]$ 看成指向 $tmp$ 上一段长为 $height[1]$ 的指针

那么指针 $dp[1]$ 与 $tmp[\ 0,…height[1]-1 \ ]$ 共同构成了 $dp[1][\ 0,…,height[1]-1\ ]$

---

dp[to]=pos, pos+=len;

与上面相同，在进入 $dfs2$ 前开好 $dp[to]$ 所需的空间，即以 $to$ 为起点的链，其长度为 $len$

而对于链上其他点(即点 $to$ 的长儿子，其长儿子的长儿子，…)，不会进入当前行，即不需开新空间

---

dp[son[cur]] = dp[cur] + 1;

即继承长儿子的答案: $dp[i][j]=dp[lson][j-1]$

数组指针形式：$dp[\ i\ ]=dp[\ lson[\ i\ ]\ ]-1$

---

dp[cur][j+1] += dp[to][j];

暴力合并轻儿子的值