题目链接

https://qduoj.com/problem/22

题目大意

n个节点的一棵树，先确定一个节点，问与其直接相连的节点的个数，与其隔一个节点相连的节点的个数，与其隔两个节点相连节点的个数……；
输入：t组数据；每组数据n，k分别代表n个城市，k是基准城市序号；n-1行道路，输入u，v，相连城市的序号。
输出：每组数据的第一行先输出全部城市被遍历需要几次，再以此输出每天遍历的城市个数。

解题思路

一眼过去直接bfs。
加个统计就行，其实这个统计也不是特别好想。
还是讲讲代码吧。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int ans[N]={1};//用来存储每天被感染的城市数，ans[0]表示第一天被感染的城市数……，初始化第一天为1
vector<int> a[N];//存城市之间的道路
int vis[N];//标记数组
int bfs(int x){
    int cnt=0,t=1,Time=0;
        //这几个变量不好理解，
        //cnt用于统计某天被感染城市总数，会不断刷新；
        //判断Time是否与昨天被感染的城市数相等，若相等了，说明cnt已经统计完成，把所以当日被感染的城市都统计上了。本质上是判断是否父亲节点全部遍历完成。
        //t用于控制ans数组的索引
    queue<int> q;//bfs所用队列
    q.push(x);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        Time++;
        for(int i=0;i<a[tmp].size();i++){
            int id=a[tmp][i];//与tmp节点相连的节点
            if(vis[id]) continue;//若与tmp节点相连的节点被访问过，continue
            cnt++;//统计
            q.push(id);
            vis[id]=1;
            //cout<<id<<endl;
        }
        if(Time==ans[t-1]) ans[t++]=cnt,Time=0,cnt=0;//若父亲节点遍历完了，cnt、Time置零，并给ans赋值。
    }
    return t-1;    
}
int main(){
    int t,n,k;
    cin>>t;
    while(t--){
        memset(vis,0,sizeof vis);//注意清空    
        cin>>n>>k;
        vis[k]=1;//注意先标记一下基准节点
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        int res;    
        cout<<(res=bfs(k))<<endl;
        for(int i=0;i<res;i++)
            cout<<ans[i]<<' ';
        cout<<endl;

                //注意清空    
        for(int i=0;i<=n;i++)
            a[i].clear();
    }
}

总结

还好，debug了一会，错以为tmp就是tmp的父亲节点了，后来才发现要标记一下才行。