[数据结构与算法]Collision (dfs深度奇偶性原理 / LCA)

div2 每日一题

Title

Solution

显然，如果两个点之间的最短路径是奇数，则是 “road”， 否则 “town”。

1. 可以用lca求出 a，b 的最近公共祖先，然后 由$$ans=dist[a]+dist[b]?dist[lca(a,b)]$$求出两个结点之间的距离。$dist[x]$ 表示 x 到根节点的距离，也即“深度”。
2. 因为只需要判断奇偶性，所以，只需判断 a，b 深度的奇偶性即可。
   显然，a，b 的深度同奇偶，则 a，b之间的距离同奇偶。

Code

const int N = 2e5 + 3, M = 1e6 + 6;
int n;
vector<int> v[N];
int d[N];

void dfs(int x, int fa)
{
	for (int i = 0; i < sz(v[x]); i++)
	{
		int y = v[x][i];
		if (y == fa) continue;
		d[y] = d[x] + 1;
		dfs(y, x);
	}
}

int main()
{
	IOS;
	int n, q; cin >> n >> q;
	for (int i = 1, x, y; i < n; i++)
		cin >> x >> y,
		v[x].push_back(y),
		v[y].push_back(x);

	dfs(1, -1);

	int x, y;
	while (q--)
	{
		cin >> x >> y;
		if (abs(d[x] - d[y]) & 1) cout << "Road\n";
		else cout << "Town\n";
	}


	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖