Title

Solution

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

1. 可以用lca求出 a，b 的最近公共祖先，然后 由 a n s = d i s t [ a ] + d i s t [ b ] − d i s t [ l c a ( a , b ) ] ans = dist[a] + dist[b] - dist[lca(a, b)] ans=dist[a]+dist[b]−dist[lca(a,b)]求出两个结点之间的距离。 d i s t [ x ] dist[x] 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
";
		else cout << "Town
";
	}


	return 0;
}