https://www.acmicpc.net/problem/9489

• Tree’s data structure
• every nodes’ parent
• adj list = ever nodes’ children
• Don’t need to save every children, just size of children is enough to solve
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 #include using namespace std; class Tree { int N, tmp; vector nodes; unordered_map parent; unordered_map> adj; public: Tree(int n): N(n) {} void input(); void makeGraph(); void printCousin(int k); }; void Tree::input() { nodes.push_back(0); for(int i = 0; i < N; i++) { cin >> tmp; nodes.push_back(tmp); } } void Tree::makeGraph() { int pp = 0, cp = 1; while(cp <= N) { parent[nodes[cp]] = nodes[pp]; adj[nodes[pp]].push_back(nodes[cp]); if(nodes[cp+1] == nodes[cp]+1) cp++; else pp++, cp++; } } void Tree::printCousin(int k) { int gp = parent[parent[k]]; vector sons = adj[gp]; int ans = 0; for(int son: sons) if(son != parent[k]) ans += adj[son].size(); printf("%d\n", ans); } int main() { int N, K; while(1) { cin >> N >> K; if (!N && !K) return 0; Tree tree(N); tree.input(); tree.makeGraph(); tree.printCousin(K); } }