[CF Round #294 div2] E. A and B and Lecture Rooms 【树上倍增】

题目链接：E. A and B and Lecture Rooms

题目大意

给定一颗节点数10^5的树，有10^5个询问，每次询问树上到xi, yi这两个点距离相等的点有多少个。

题目分析

若 x==y 直接返回 n。

先求出 x, y 两个点的中点。

先求出 LCA(x, y) = z，假设 Depth[x] >= Depth[y] ，若Depth[x] == Depth[y] ，那么 z 就是它们的中点。

答案就是，n - Size[fx] - Size[fy]，fx 是从x向上跳，一直跳到 z 的一个孩子就停止，这个孩子就是 fx。

否则中点一定在从 x -- z -- y 的路径上 x -- z 的一段，为 Jump(x, t) ，t 是 x -- z -- y 长度的一半。如果 x -- z -- y 的长度是奇数，就返回 0。

这个 Jump(a, b) 就是用倍增来求的。

答案就是， Size[o] - Size[fx]。这里的o是中点，fx是从x向上跳，跳到o的一个孩子就停止。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int MaxN = 100000 + 5, MaxLog = 19 + 5;

int n, m;

int Depth[MaxN], Father[MaxN], Jump[MaxN][MaxLog], Size[MaxN];

struct Edge

{

	int v;

	Edge *Next;

} E[MaxN * 2], *P = E, *Point[MaxN];

inline void AddEdge(int x, int y)

{

	++P; P -> v = y;

	P -> Next = Point[x]; Point[x] = P;

}

void DFS(int x, int Dep, int Fa)

{

	Depth[x] = Dep;

	Father[x] = Fa;

	Size[x] = 1;

	for (Edge *j = Point[x]; j; j = j -> Next)

	{

		if (j -> v == Father[x]) continue;

		DFS(j -> v, Dep + 1, x);

		Size[x] += Size[j -> v];

	}

}

void Prepare()

{

	for (int i = 1; i <= n; ++i) Jump[i][0] = Father[i];

	for (int i = 1; i <= n; ++i)

		for (int j = 1; j <= 18; ++j)

			Jump[i][j] = Jump[Jump[i][j - 1]][j - 1];

}

int JumpUp(int x, int y)

{

	int ret = x;

	for (int i = 0; i <= 18; ++i)

		if (y & (1 << i)) ret = Jump[ret][i];

	return ret;

}

int LCA(int x, int y)

{

	if (Depth[x] < Depth[y]) swap(x, y);

	int Dif;

	Dif = Depth[x] - Depth[y];

	if (Dif) x = JumpUp(x, Dif);

	if (x == y) return x;

	for (int i = 18; i >= 0; --i)

	{

		if (Jump[x][i] != Jump[y][i])

		{

			x = Jump[x][i];

			y = Jump[y][i];

		}

	}

	return Father[x];

}

int Query(int x, int y)

{

	if (x == y) return n;

	if (Depth[x] < Depth[y]) swap(x, y);

	int z, tx, ty, fx, fy, t, o;

	z = LCA(x, y);

	tx = Depth[x] - Depth[z];

	ty = Depth[y] - Depth[z];

	t = tx + ty;

	if (t & 1) return 0;

	if (Depth[x] == Depth[y])

	{

		fx = JumpUp(x, tx - 1);

		fy = JumpUp(y, ty - 1);

		return n - Size[fx] - Size[fy];

	}

	else

	{

		t >>= 1;

		o = JumpUp(x, t);

		fx = JumpUp(x, t - 1);

		return Size[o] - Size[fx];

	}

}

int main()

{

	scanf("%d", &n);

	int a, b;

	for (int i = 1; i <= n - 1; ++i)

	{

		scanf("%d%d", &a, &b);

		AddEdge(a, b);

		AddEdge(b, a);

	}

	scanf("%d", &m);

	DFS(1, 0, 0);

	Prepare();

	for (int i = 1; i <= m; ++i)

	{

		scanf("%d%d", &a, &b);

		printf("%d\n", Query(a, b));

	}

	return 0;

}

　　

[CF Round #294 div2] E. A and B and Lecture Rooms 【树上倍增】的相关教程结束。