人生第一道A掉的提高组T3= =

倍增+LCA 就能轻松AC了

但lbn大神让我去学树剖LCA 而我连树剖都不会 结果被大D一通

void Mul()
{
	for (int i = 1;i <= 14;i++) //14是logn
		for (int j = 1;j <= n;j++)
			if (p[j][i-1] != -1)
			{
				p[j][i] = p[p[j][i-1]][i-1];
				dis[j][i] = min(dis[j][i-1],dis[p[j][i-1]][i-1]);//距离
			}
}

int LCA(int a,int b)
{
	if (deep[a] < deep[b]) swap(a,b);
	int mina = 100000000,minb = 100000000;
	int t = deep[a] - deep[b];
	for (int i = 0;i <= 14;i++)
		if (t&(1 << i)) mina = min(mina,dis[a][i]),a = p[a][i];//到同一层
	if (a == b) return mina;
	for (int i = 14;i >= 0;i--)
		if (p[a][i] != -1&& p[a][i] != p[b][i])
		{
			mina = min(mina,dis[a][i]);
			a = p[a][i];
			minb = min(minb,dis[b][i]);
			b = p[b][i];
		}
	if (a == b) return min(mina,minb);
	return min(min(mina,dis[a][0]),min(minb,dis[b][0]));
}