#25579: 95% 求大神幫忙


johnnyli122022@gmail.com (李小佑)

School : 臺北市立成功高級中學
ID : 144028
IP address : [61.228.55.5]
Last Login :
2022-06-06 14:55:20
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [61.228.40.180] | Post Date : 2021-06-03 20:44

#include <bits/stdc++.h>

#define N 100020

using namespace std;

 

int main(){

int n, c;

int parent[N]={}, h[N]={}, children[N]={};

queue<int> Q;

scanf("%d", &n);

for(int i=1; i<=n; i++){

scanf("%d", &children[i]);

if(children[i]==0) Q.push(i);

for(int j=1; j<=children[i]; j++){

scanf("%d", &c);

parent[c]=i;

}

long long total=0;

int root;

while(1){

int v=Q.front();

Q.pop();

int p=parent[v];

total+=h[v];

if(p==0){

root=v;

break;

}

h[p]=max(h[p],h[v]+1);

children[p]-=1;

if(children[p]==0){

Q.push(p);

}

}

printf("%d\n%d\n", root, total);

}

 
ZeroJudge Forum