B3861题解

· · 题解

原题传送门

0.题解背景

WA 哦，这么水的暂无评定题，赶紧水一篇题解。

1.题目分析

题目意思很 easy，简单概括一下：

每个结点的权值都是 1，你需要对每个结点 i 求出 i 的子树和，也就是子树中有多少个结点。

看完题目，很容易就能想到宽搜。

2.解题思路

瞅一眼数据，emm...，1 \le n \le 1000，宽搜完全木有问题。

3.AC code

贴代码啦!

#include<bits/stdc++.h>//万能的头 
#define f(i,j,k) for(i=j;i<=k;i++)//作者懒地打for 
using namespace std;
int n,i,j,t,w,x,b[1010],f[1010],xx;
vector<int>a[1010];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//简易·加速代码 
    cin>>n;
    f(i,2,n)cin>>x,a[x].push_back(i);//建边 
    f(i,1,n){
        f(j,1,n)f[j]=0;
        t=w=1;//宽搜！启动！！！ 
        b[1]=i;//入队 
        f[i]=1;//计入做过 
        while(t<=w){
            x=b[t];//取出队头 及父亲 
            for(j=0;j<a[x].size();j++){
                xx=a[x][j];//取出儿子 
                if(f[xx]==1)continue;
                b[++w]=xx;f[xx]=1;//入队 
            }
            t++;//出队 
        }
        cout<<w<<"\n";//输出 
    }
    return 0;//完成！！！ 
}

热烘烘的题解~~ 给个赞啦！