题目内容
注意读题:本题的题意是让我们求出仓鼠可能在多少个位置。由于trap在距离d以内可以捕获仓鼠,所以仓鼠一定在d以外,题目要求求的是距离根节点距离大于d的点的个数
解题思路
给出了边的条数是点数减一,所以这张图是一棵树。使用dfs遍历一遍树然后统计距离大于d的点数即可
坑点:
- 本题有多组测试数据,每次要重新初始化一遍相关变量。
- 遍历树的时候记得打
vis
标记(因为太久没做树的题了所以忘记打标记造成无限递归 - 节点是从0开始编号的
这里使用了OOP编程(真的香
每次处理新的测试数据时清空即可
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int T;
const int maxn=100000+5;
class tree//tree类
{
public:
vector<int> g[maxn];//邻接表存树
bool vis[maxn];//vis数组
int depth[maxn];//记录每个节点的深度
int n,d;//注意节点从0开始编号
inline void ins(int x,int y)//插入操作
{
g[x].push_back(y);
g[y].push_back(x);
}
void dfs(int cur,int dep)//dfs
{
//printf("%d ",cur);
depth[cur]=dep;//更新遍历到的节点的深度
for(int i=0;i<g[cur].size();i++)//寻找该节点与哪些节点相连
if(!vis[g[cur][i]])//判重
{
vis[g[cur][i]]=1;
dfs(g[cur][i],dep+1);//继续遍历
}
return;
}
int ans()//统计答案的函数
{
int ret=0;
for(int i=0;i<n;i++)
if(depth[i]>d)
ret++;//统计答案
return ret;
}
void clear()//每次操作前记得清空
{
n=d=0;
memset(depth,0,sizeof(depth));
memset(g,0,sizeof(g));//我也是服了居然vector可以用memset
memset(vis,0,sizeof(vis));
vis[0]=1;//vis[0]必须设为1,不然会WA
}
}t;
int main()
{
scanf("%d",&T);
while(T--)
{
t.clear();//每次使用记得清空
scanf("%d %d",&t.n,&t.d);
for(int i=1;i<t.n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
t.ins(x,y);
}
t.dfs(0,0);//开始遍历,从0号节点开始
printf("%d\n",t.ans());
}
return 0;
}
反思
太久没做树的题果然会手生qwq
留言