微软2014编程之美初赛第一场—

微软2014编程之美初赛第一场——题目2 : 树

【来源】

题目2 : 树

【分析】

依据输入情况建立起树的模型。树的表示是一个表明父亲节点的数组。核心算法有两个：

计算某一节点的深度。用循环实现，一直向上找父亲节点，直到找到根节点。计算循环的次数即为深度。
计算某一节点的全部子节点。用递归实现。

本题在实现上节点的命名从0至N-1，与题目描写叙述不同。

【代码】

#include <iostream>
#include <vector>
using namespace std;

vector<int> children(int node, int* father, int n)
{
    vector<int> res;
    for (int i = 0; i < n; ++i){
        if (father[i] == node){
            res.push_back(i);
            vector<int> cs = children(i, father, n);
            if (cs.size() != 0){
                for (int j = 0; j < cs.size(); ++j){
                    res.push_back(cs[j]);
                }
            }
        }
    }

    return res;
}
int main()
{
    int T;
    cin >> T;
    for (int c = 0; c < T; ++c){
        int N;
        cin >> N;
        int* w = new int[N];
        for (int i = 0; i < N; ++i){
            w[i] = 0;
        }
        int* father = new int[N];
        for (int i = 1; i < N; ++i){
            cin >> father[i];
            father[i]--;
        }
        // build the tree
        int* dep = new int[N];
        dep[0] = 1;
        for (int i = 1; i < N; ++i){
            int d = 1;
            int node = i;
            while (node != 0){
                node = father[node];
                ++d;
            }
            dep[i] = d;
        }

        int Q;
        cin >> Q;
        for (int i = 0; i < Q; ++i){
            int u, l, r, delta;
            cin >> u >> l >> r >> delta;
            //do the operation
            vector<int> childs = children(u-1, father, N);

            for (int j = 0; j < childs.size(); ++j){
                if (dep[childs[j]] >= l && dep[childs[j]] <= r){
                    w[childs[j]] += delta;
                }
            }

        }

        //calc hash
        int MOD = 1000000007;
        int MAGIC = 12347;
        int Hash = 0;
        for (int i = 0; i < N; ++i){
            Hash = (Hash*MAGIC + w[i]) % MOD;
        }
        //output
        cout << "Case " << c+1 << ": " << Hash << endl;
    }

    system("pause");
    return 0;
}

【点评】

本题考查树的相关知识以及递归程序的设计。重点在于计算某个节点的深度和计算某个节点的全部子节点。