树，偏短代码-创新互联

（未更新完整，见一道写一道）

这篇写偏向于竞赛的短代码，长代码会另写一篇

我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。

FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为的 01 串 S可以构造出一棵 FBI 树 T，递归的构造方法如下：

1. T的根结点为 R，其类型与串 S的类型相同；

2. 若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S1和 S2；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R的右子树T2。

现在给定一个长度为的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

输入

第一行是一个整数N(0≤N≤10)，

第二行是一个长度为的 01 串。

输出

一个字符串，即 FBI 树的后序遍历序列。

Input

3
10001011

Output

IBFBBBFIBFIIIFF

（此题概念挺新鲜的，代码倒是还好）

#includeusing namespace std;

int main() {
    int n;
    cin >>n;
    string t;
    cin >>t;
    string s = " ";
    s += t;
    stackss;
    int a[11] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
    for (int i = 1; i< s.size(); i++) {
        if (s[i] == '0')
            ss.push('B');
        else
            ss.push('I');
        cout<< ss.top();
        for (int j = 0; j< 11; j++) {
            if (i % a[j] == 0) {
                int t = ss.top();
                ss.pop();
                int u = ss.top();
                ss.pop();
                if (t == 'B' && u == 'B')
                    ss.push('B');
                else if (t == 'I' && u == 'I')
                    ss.push('I');
                else
                    ss.push('F');
                cout<< ss.top();
            } else
                break;
        }

    }
}

题目来源：Codeforces Round #790 (Div. 4)

题意：已知某棵树总共几个结点，然后再给出从2-n的每个结点的父节点。然后给出这棵树从1-n的结点对应的颜色（B黑W白），然后计算有几颗子树是黑白平衡树

Sample Input

3
7
1 1 2 3 3 5
WBBWWBW
2
1
BW
8
1 2 3 4 5 6 7
BWBWBWBW

Sample Output

2
1
4

蒋神代码%%%%

#includeusing i64 = long long;

void solve() {
    int n;
    std::cin >>n;
    std::vectors(n), p(n);
    p[0] = -1;
    for (int i = 1; i< n; i++) {
        std::cin >>p[i];
        p[i]--;
    }
    for (int i = 0; i< n; i++) {
        char c;
        std::cin >>c;
        s[i] = c == 'W' ? 1 : -1;
    }
    for (int i = n - 1; i >0; i--) {
        s[p[i]] += s[i];
    }
    std::cout<< std::count(s.begin(), s.end(), 0)<< "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >>t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧