B: 树上分支
共 2365字，需浏览 5分钟
·
2021-03-27 00:19
B: 树上分支
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
有的时候，题目和内容是没有一点关系的。
当然，作为一个有责任心的出题者，会把题目和名字紧紧联系在一起。
显然，小花不是一个有责任心的出题者。
由于他想尽早的完成出题任务，于是他把出题的流程抽象成了一棵树。
例如，当出完题目后，小花可以选择先写标程，或是先造数据。但找人验题，一定是在造完数据以后。他现在正处在其中的某个阶段，你可以把所有的阶段都视为一个点。
烦人的 boss 又在催促他,并询问最快还有多久才能到第 x 个阶段。所有的询问相互独立。
输入格式
第一行一个整数 T,代表 T 组数据。(T<=500)
接下来每行三个数 n，m，r。代表有 n 个阶段，m 个询问,小花现在正处在 第 r 个阶段。(1<=n,m<=100000)
接下来 n-1 行，每行两个数，u,v,代表 v 阶段在 u 阶段之后。(1<=u,v<=n)
接下来一行有 m 个数，代表 boss 询问到第 x 个阶段还有多久。(1<=x<=n)
输出格式
对于每组数据，输出 m 个数，代表小花最快还有几步才能到要求的阶段。
如果小花已经完成了 boss 询问的那个阶段，那么对此询问输出 0。
如果无法确定小花是不是完成了那个阶段，输出-1。
如果询问的就是小花所在的阶段，输出 0。
每个询问后输出一个空格，每组数据后输出一个换行。
输入样例 复制
1
5 2 1
1 2
1 3
2 4
2 5
3 4
输出样例 复制
1 2
思路：
n个节点，n-1条边，是一棵树，这题就是在一棵树上对祖先遍历更新一遍，再对子节点遍历更新一遍，然后照着题目的问题输出即可。BFS和DFS都可以。
bfs和dfs的写法都给了，注意，有的oj上使用cin和cout即使关了流也可能超时，建议使用scanf和printf读入与读出。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
int n,m,r,t;
double a,b;
vector<int> edge[maxn];
vector<int> fa[maxn];
int dis[maxn];
void bfs1(int x)
{
queue<int> que;
que.push(x);
dis[x]=0;
while(!que.empty())
{
int z=que.front();
que.pop();
for(int i=0;i<fa[z].size();i++)
{
int y=fa[z][i];
dis[y]=0;
que.push(y);
}
}
return;
}
void bfs(int x)
{
queue<int> que;
dis[x]=0;
que.push(x);
while(!que.empty())
{
int z=que.front();
que.pop();
for(int i=0;i<edge[z].size();i++)
{
int y=edge[z][i];
dis[y]=dis[z]+1;
que.push(y);
}
}
return;
}
int main()
{
scanf("%d",&t);
while(t--)
{
cin>>n>>m>>r;
for(int i=1;i<=n;i++)
{
edge[i].clear();
fa[i].clear();
dis[i]=-1;
}
n=n-1;
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
edge[a].push_back(b);
fa[b].push_back(a);
}
dis[r]=0;
bfs1(r);
bfs(r);
while(m--)
{
int a;
scanf("%d",&a);
printf("%d ",dis[a]);
}
printf("\n");
}
return 0;
}