社区讨论
dalao为甚会RE
P1600[NOIP 2016 提高组] 天天爱跑步参与者 7已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi6lhfms
- 此快照首次捕获于
- 2025/11/20 06:49 4 个月前
- 此快照最后确认于
- 2025/11/20 06:49 4 个月前
dfs
CPP#include <iostream>
#include <cstring>
using namespace std;
bool vis[101010],flag;
long long a[101010],ans[101010],map[10101][10101],u,v,n,m;
void dfs(long long s,long long e,long long t)
{
if(flag) return;
if(vis[s]) return;//cout<<st<<" "<<t<<endl;
vis[s]=1;
if(s==e)//if(a[ed]==t) ans[ed]++;
flag=1;
if(a[s]==t) ans[s]++;
for(long long i=1;i<=n;i++)
if(map[s][i] && !vis[i])
dfs(i,e,t+1);
}
int main()
{
cin>>n>>m;
for(long long i=1;i<n;i++)
{
cin>>u>>v;
map[u][v]=1;
map[v][u]=1;
}
for(long long i=1;i<=n;i++)
cin>>a[i];
for(long long i=1;i<=m;i++)
{
memset(vis,0,sizeof(vis));
flag=0;long long s,e;
cin>>s>>e;
dfs(s,e,0);
}
for(long long i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
/*
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
*/
/*
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
*/
回复
共 6 条回复,欢迎继续交流。
正在加载回复...