二、阅读程序（程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序（3）

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

const int mod = 1000000000 + 7;
int w0[100005];
int w1[100005];
int w2[100005];
int n, m, k, f[100005], d[100005], id[100005];
vector<int> e[100005];

void dfs(int u, int fa) {
    d[u] = d[fa] + 1;
    f[u] = fa;
    for (auto &v : e[u]) if (v != fa) {
        dfs(v, u);
    }
}

bool cmp(int a, int b) {
    return d[a] < d[b];
}

int main() {
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0); // ①
    for (int i = 1; i <= m; i++) {
        int x, w;
        cin >> x >> w;
        w1[x] = (w1[x] + w) % mod;
        w2[x] = (w2[x] + w) % mod;
    }
    for (int i = 1; i <= n; i++)
        id[i] = i;
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= k; i++) {
        for (int j = n; j >= 1; j--) {
            int x = id[j];
            for (auto &y : e[x]) if (y != f[x]) {
                w1[y] = (w1[y] + w1[x]) % mod;
            }
            w1[x] = 0;
        }
        for (int x = 1; x <= n; x++)
            w1[x] = (w1[x] - w0[x] + mod) % mod,
            w0[x] = 0;
        for (int j = 1; j <= n; j++) { // ②
            int x = id[j];
            if (f[x]) {
                w1[f[x]] = (w1[f[x]] + w2[x]) % mod;
                w2[f[x]] = (w2[f[x]] + w2[x]) % mod;
                w0[x] = (w0[x] + w2[x]) % mod;
                w2[x] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << w1[i] << " ";
    return 0;
}

保证输入的 $n,m$ 不超过 $10^5$，$k$ 不超过 20，且 $1 \le x_i \le n$，$0 \le w_i < 10^9+7$。

1. 对于以下输入数据，输出结果为（ ）。

9 9 2
1 2
1 7
2 3
2 4
7 8
4 5
4 6
8 9
1 1
2 10
3 100
4 1000
5 10000
6 100000
7 1000000
8 10000000
9 100000000

{{ select(1) }}

• 10001100 1110000 1001 101 100010 10010 100000010 1 1000000
• 0 0 1 1 10 10 0 1 1000000
• 11001110 1111100 1001 110101 100010 10010 110000010 100000001 1000000
• 11001111 1111112 1121 111121 112010 112010 111000012 112000001 121000000