#include <bits/stdc++.h>
using namespace std;
const int maxi = 6e5+9;
int vi = 0;
vector<int> graf[maxi];
vector<int> roots;
vector<int> konf[maxi];
int width[maxi];
int dfs(int w){
if(graf[w].size() == 0) width[w] = 1;
else for(int& v : graf[w]){width[w] += dfs(v);}
return width[w];
}
int main(){
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int k, n;
cin >> k >> n;
for(int i = 0; i < n; i++){
roots.push_back(vi);
konf[1].push_back(vi);
vi++;
}
for(int i = 2; i <= k; i++){
cin >> n;
for(int j = 0; j < n; j++){
int a; cin >> a; a--;
konf[i].push_back(vi);
if(a < 0) roots.push_back(vi);
else graf[konf[i-1][a]].push_back(vi);
vi++;
}
}
for(int& v : roots){
dfs(v);
}
int wynik = 0;
for(int i = 1; i <= k; i++){
int cur = 0;
for(int j = 0; j < konf[i].size(); j++){
//cout << konf[i][j] << ' ';
//cout << width[konf[i][j]] << ' ';
cur += width[konf[i][j]];
}
//cout << endl;
wynik = max(wynik, cur);
}
cout << wynik << endl;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <bits/stdc++.h> using namespace std; const int maxi = 6e5+9; int vi = 0; vector<int> graf[maxi]; vector<int> roots; vector<int> konf[maxi]; int width[maxi]; int dfs(int w){ if(graf[w].size() == 0) width[w] = 1; else for(int& v : graf[w]){width[w] += dfs(v);} return width[w]; } int main(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int k, n; cin >> k >> n; for(int i = 0; i < n; i++){ roots.push_back(vi); konf[1].push_back(vi); vi++; } for(int i = 2; i <= k; i++){ cin >> n; for(int j = 0; j < n; j++){ int a; cin >> a; a--; konf[i].push_back(vi); if(a < 0) roots.push_back(vi); else graf[konf[i-1][a]].push_back(vi); vi++; } } for(int& v : roots){ dfs(v); } int wynik = 0; for(int i = 1; i <= k; i++){ int cur = 0; for(int j = 0; j < konf[i].size(); j++){ //cout << konf[i][j] << ' '; //cout << width[konf[i][j]] << ' '; cur += width[konf[i][j]]; } //cout << endl; wynik = max(wynik, cur); } cout << wynik << endl; } |
English