自动搬运

查看原文

来自洛谷，原作者为

	lizhengdong ʕ̯•͡˔•̯᷅ʔ这个家伙不是家伙，是只被眷顾的栗子，举个栗子，比如栗子被摔了，就会出现重栗势能转化为动能，产生了动栗，栗子就会撞G地面，承受巨大的栗量，就会出现“震荡”等现象。emm···

搬运于2025-08-24 21:15:33，当前版本为作者最后更新于2023-10-09 19:56:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

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;//完成！！！ 
}

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