长链剖分入坑记

给定一棵以 1 为根，n (n <= 1e6)个节点的树。
令 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。
对于每个点，求一个最小的 k，使得 d(u,k) 最大。

输入输出样例
输入 #1复制
4
1 2
2 3
3 4
输出 #1复制
0
0
0
0
输入 #2复制
4
1 2
1 3
1 4
输出 #2复制
1
0
0
0
输入 #3复制
4
1 2
2 3
2 4
输出 #3复制
2
1
0
0

限制
4500ms 512MB

//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
//#define LOCAL
#define ri register int
const int maxn = 1e6+5;
int n, head[maxn], cnt, dep[maxn], height[maxn], son[maxn], *dp[maxn], tmp[maxn], *pos, ans[maxn];
struct Arc
{
	int from, to, nxt;
} g[maxn << 1];

inline void addarc(int from, int to)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

void dfs1(int cur, int fa)
{
	height[cur] = dep[cur] = dep[fa] + 1;
	for (ri h = head[cur], to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (to ^ fa)
		{
			dfs1(to, cur);
			if (height[to] > height[cur])
			{
				height[cur] = height[to];
				son[cur] = to;
			}
		}
	}
}

void dfs2(int cur, int fa)
{
	dp[cur][0] = 1;
	if (son[cur])
	{
		dp[son[cur]] = dp[cur] + 1;
		dfs2(son[cur], cur);
		ans[cur] = ans[son[cur]] + 1;
	}
	for (ri h = head[cur], to, len; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		len = height[to] - dep[to] + 1;
		if (to ^ fa && to ^ son[cur])
		{
			dp[to] = pos, pos += len;
			dfs2(to, cur);
			for (ri j = 0; j < len; j++)
			{
				dp[cur][j + 1] += dp[to][j];
				if (dp[cur][j + 1] > dp[cur][ans[cur]] || dp[cur][j + 1] == dp[cur][ans[cur]] && ans[cur] > j + 1)
				{
					ans[cur] = j + 1;
				}
			}
		}
	}
	if (dp[cur][ans[cur]] == 1)
	{
		ans[cur] = 0;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	for (ri i = 1, a, b; i < n; i++)
	{
		scanf("%d%d", &a, &b);
		addarc(a, b);
		addarc(b, a);
	}
	dfs1(1, 0);
	pos = tmp;
	dp[1] = pos, pos += height[1];
	dfs2(1, 0);
	for (ri i = 1; i <= n; i++)
	{
		printf("%d\n", ans[i]);
	}
	return 0;
}

line 8
dep[i]是节点i在树中的深度, dep[1]=1, height[i]=max{dep[j] : j 属于i为根的子树}
son[i]在i为根的子树中并且满足 dep[son[i]] = height[i], 即son[i]就是i的长儿子
dp就是上面在暴力O(n^2)中论及的二维数组
tmp+pos的意义后面再讲
ans[i]是节点i处答案

line 20
dfs1的目的是预处理出son、height

line 87
根据上面暴力dp算法的思路，dp[1]显然需要确定的是 dp[1][0,...,height[1] - dep[1]]
即 dp[1][0,...,height[1] - 1], 所以这一行让dp[1][0,...height[1] - 1]在tmp上开辟好空间
即在tmp上开辟一段长度为 height[1]的数组. 这个空间就是用来存储dp[1][0,...height[1]-1]的

line 53
和line 87 是一样的, 就是进入dfs之前先在tmp上开辟好空间. 所以tmp和pos的作用就是开辟长链要占据的空间
这里要注意, line53的to其实是一根长链的起点.
包括line87行, 1不也是长链的起点吗? 所以其实line53、line 87行做的事情就是为长链在tmp上开辟空间.
对于在一根长链上起点之外的节点, 它在程序运行的过程中仅仅会进入43行, 是不会新开辟空间的.
而开辟的空间长度恰好就是该长链的长度————就拿53行的to来讲, 它作为长链的起点, 它领头的长链长度就是
50行的len,所以我们就知道为什么tmp只需要maxn的空间复杂度了————这是因为上面说的长链的性质2决定的.
这里开辟空间形象的画出来就是下面的图2

line 43
就是上面的式(1). line53说了, 长儿子son[cur]并不会引起在tmp上空间的开辟, 只有轻儿子to(其实轻儿子是
一段新的长链的领头人)才会引发tmp数组上空间的开辟. 所以cur的长儿子son[cur]的dp数组————
dp[son[cur]]就应该在为cur开辟的tmp上的空间进行修改(这里cur是长链的领头人哈~ 例如图1中2就是2--6这
根长链的领头人, 1就是1--3--4---7这根长链的领头人， 5就是5--5这根长链的领头人).

line 45
cur直接继承长儿子的答案

line 57
其实就是图2中的用to领头的长链的dp值去更新cur领头的长链

line 58
更新答案, 这没什么好说的.