题解 P4615 【[COCI2017-2018#5] Birokracija】

· · 题解

这道题的恶心内存与恶心数据导致存图 只 不只能用链式前向星(个人不常用STL),于是......

永远喜欢链式前向星!!!

Code:

#include<cstdio>
#define reg register
#define ll long long
using namespace std;
inline int Read(){//快读,优化时间
    reg int x=0,f=1;reg char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(ch>='0' && ch<='9'){
        x=(x<<3)+(x<<1)+(ch&15);
        ch=getchar();
    }
    return x*f;
}
inline void Print(const ll x){//快输,也是优化时间
    if(x<0){putchar('-');Print(-x);}
    if(x<10) putchar(x+48);
    else{Print(x/10);putchar(x%10+48);}
}
inline void Println(const ll x){Print(x);putchar('\n');}
ll b[200105],c[200105];
int n,head[200105],top;//上司关系不会超过人数,所以可以用int
struct p{
    int to,nxt;
}e[200105];//链式前向星存图
inline void dfs(const int Number){
    b[Number]=1;
    for(reg int i=head[Number];i;i=e[i].nxt){
        reg int some=e[i].to;
        dfs(some);//统计他的助手
        c[Number]+=c[some];
        b[Number]+=b[some];
    }
    c[Number]+=b[Number];
}
inline void add(int u,int v){//链式前向星建边
    e[++top].to=v;
    e[top].nxt=head[u];
    head[u]=top;
}
int main(){
    n=Read();
    for(reg int i=2;i<=n;++i){
        reg int x=Read();
        add(x,i);
    }
    dfs(1);//慢慢统计吧......
    for(reg int i=1;i<=n;++i){
        Print(c[i]);putchar(' ');
    }
    putchar('\n');
    return 0;
}

链式前向星是解决图论问题的利器,大家一定要学会哦