题解 SP34009 【CTTC - Counting Child】
蒟蒻来发第二个题解啦！
这道题目提交了三次才过 。我绝对不会告诉你们我是写错了格式 ，把 Case 写成了 case 。
好的，言归正传 ：
做这一题你首先要学会什么是树 ，什么是树的遍历。
如果不知道就找一下万能的百度吧 ！
好 ， 拿到这一道题目首先想问 ， 每个节点不是只能访问一次吗 ？ 为什么遍历每个节点有两个呢 ？
想了十分钟才想明白 好菜， 像下面这个只有三个节点的树。（画图技术不是很好请谅解）
它的遍历顺序是 1 2 2 3 3 1 .
观察这个序列 ， 发现了什么 ？
多了一个回溯的顺序
也就是说，当输入一个节点的时候，前面没有 DFS 这个节点，则 DFS 这个节点，如果前面 DFS 过了，那么就跳出这个 DFS 。
根据 DFS 的特点（ 深度优先，当遍历到一个节点时，接下来就遍历这个数的子树 ） ，我们可以得出一个结论：
- 设第一个输入的数是 \(a_1\) ，第二个数是 \(a_2\) ，第三个数是 \(a_3\) ......
- 在 a 这个数列里面，当 \(a_l = a_r\) 的时候，区间 [l,r] 就是 \(a_l\) 这个节点的 DFS 过程。
DFS，DFS，DFS！这是怎么实现的呢？
递归。一想到递归，我就想到了栈（因为这个题目给了回溯的过程）。
那么我们可以用一个栈来模拟 DFS 的过程。做法如下：
- 当输入一个节点的编号的时候，如果这个节点还没有输入国（就是还没有开始 DFS ）我们就把这个节点的编号加入到栈里面。
- 如果这个节点已经输入过了，那么说明这是个回溯的过程，就把当前的栈顶出栈（因为 DFS 的特性，最后递归的一定是最先返回的，所以我们能肯定当前出栈的一定就是输入的这个元素，不信可以试试看）
- 在回溯的过程当中，我们先把栈顶出栈，再把出栈后的栈顶的儿子的数量+1.（还是因为 DFS 的特性，我们搜完这个节点，返回这个节点的父节点的位置，而我们返回的这个父节点就多了一个儿子）
看起来貌似可以了？模拟一下第一个样例：
3
1 2 2 3 3 1
最开始栈为空，再 1 入栈， 2 入栈， 2 出栈，此时 1 的儿子数量 +1 ， 3 入栈， 3 出栈， 1 的儿子数量加 1 , 1 出栈，结束。
1有2个儿子，2 ， 3 没有儿子。Great！正确！
但是你光会这个没有用，还要注意一点细节的东西：
- 输出格式别搞错了，我就这样WA了两次
- 本题有多组测试数据，输入用的数组可以不清 0 ，但是统计数据一定要清 0！
- 是输入 n*2 个节点，而不是 n 个！
好了，说了这么多，给个你们最喜欢的代码：
#include<bits/stdc++.h> //万能头好评
using namespace std; //个人习惯
int t,n,a[201],b[101];bool f[101]; //t表示测试数据个数，a是输入的数组，b是统计答案用的数组，f标记有没有入过栈。
stack <int> s; //当然您高兴的话手写栈也是可以的
int main(){
ios::sync_with_stdio(false); //取消同步
cin>>t;
for(int i=1;i<=t;i++){
cin>>n;
for(int j=1;j<=n*2;++j){
cin>>a[j]; //输入一个节点
if(!f[a[j]]){ //如果没有入过栈
s.push(a[j]);f[a[j]]=true; //那就入栈并标记
}
else if(s.top()!=1){ //否则就出栈，并且把父节点的儿子个数+1.
//需要注意的是，如果栈里面只有1一个元素，会因为栈空了导致RE，一定要特判
s.pop();b[s.top()]++;
}
}
cout<<"Case "<<i<<":"<<endl; //格式别搞错了
for(int i=1;i<=n;++i) cout<<i<<" -> "<<b[i]<<endl;
memset(b,0,sizeof(b));
memset(f,false,sizeof(f)); //重新初始化。
s.pop();cout<<endl; //注意格式，并且还要把最后剩下的 1 删除。
}
}
一定要注意细节哦！（防作弊大法好）
个人认为这道题目的难度是普及-，主要是能想到栈的应用。
代码细节倒不是很多，主要就是判断一下栈里面只有元素 1 这一种可能