解题报告 HDU4707 Pet

题目内容

HDU4707

注意读题：本题的题意是让我们求出仓鼠可能在多少个位置。由于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