#P12365. 相逢是首歌

本文主要是介绍#P12365. 相逢是首歌，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

monkey A与monkey B住在一颗树上，每天他们都会相约一起出去玩。

q次询问，每次询问给两个点x和y，代表他们各自的出发点，他们以相同的速度，沿着二者的最短路前进. 问二者会在点上相遇，还是在边上相遇。

Format

Input

第一行给出N，Q 接下来N-1行，描述这个树 接下来Q行，每行给出x,y

N<=1e5

Q<=1e5

Output

如果在点上相遇输出Town,否则输出Road

Samples

输入数据 1

4 1
1 2
2 3
2 4
1 2

Copy

输出数据 1

Road

Copy

输入数据 2

5 2
1 2
2 3
3 4
4 5
1 3
1 5

Copy

输出数据 2

Town
Town

---

思路

我们可以把一棵树的深度分为奇数和偶数，然后查询时如果x和y深度奇偶性相同，则说明会在点上，否则说明在边上。具体可以看代码。

---

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>vec[1000001];
int vis[10000001],n,q,x,y;
void dfs(int x,int dep,int fa)
{if(dep % 2 == 0) vis[x] = 1;else vis[x] = 2;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa)dfs(vec[x][i],dep + 1,x);
}
signed main()
{cin>>n>>q;for(int i = 1;i < n;i++){cin>>x>>y;vec[x].push_back(y);vec[y].push_back(x);}dfs(1,0,0);while(q--){cin>>x>>y;if(vis[x] == vis[y]) cout<<"Town"<<endl;else cout<<"Road"<<endl;}return 0;
}

这篇关于#P12365. 相逢是首歌的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---