@[JeffWang2019](/user/219935) 为啥是`-dist[]`啊,您`dij`跑负边权?
by ADay @ 2020-08-30 00:14:34
@[JeffWang2019](/user/219935) 还有统计答案是`dist[i]<=d`吧
by ADay @ 2020-08-30 00:17:06
@[JeffWang2019](/user/219935) 改一下就行了
```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
struct no
{
int to,w,next;
}e[200005];
priority_queue<pair<int,int> >q;
int dist[100005],head[100005];
int n,d,cnt=0,ans=0;
bool vis[100005];
void add(int u,int v,int w)
{
e[++cnt]=(no){v,w,head[u]};
head[u]=cnt;
}
void dij(int s)
{
for(int i=1;i<=n;i++)
{
if(i==s)
{
dist[i]=0;
}
else
{
dist[i]=inf;
}
}
q.push(make_pair(dist[s],s));
while(!q.empty())
{
int dis=q.top().first,x=q.top().second;
q.pop();
if(vis[x])
{
continue;
}
vis[x]=true;
if(dis>dist[x])
{
continue;
}
for(int i=head[x]; i; i=e[i].next)
{
int y=e[i].to,w=e[i].w;
if(!vis[y]&&dist[y]>dist[x]+w)
{
dist[y]=dist[x]+w;
q.push(make_pair(dist[y],y));
}
}
}
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v,1);
add(v,u,1);
}
dij(1);
for(int i=2;i<=n;i++)
{
if(dist[i]<=d)
{
ans++;
}
}
printf("%d",ans);
return 0;
}
```
by ADay @ 2020-08-30 00:19:07
这题不是树的操作吗,为啥要dij啊
by WanderingTrader @ 2020-08-30 08:09:01
@[ADay](/user/312393) 我想省事于是把模板复制过来又改了改……
by JeffWang2019 @ 2020-08-30 10:06:10
这题不是dfs求深度就好了嘛,复制模板也不是瞎复制吧
by namelessgugugu @ 2020-08-30 12:15:12
@[欧阳达晟](/user/244204) ……
by JeffWang2019 @ 2020-08-30 21:22:43
@[ADay](/user/312393) 万分感谢,AC了!
by JeffWang2019 @ 2020-08-30 21:24:38