In a country, the relationship between people can be indicated by a tree. If two people are acquainted with each other, there will be an edge between them. If a person can get in touch with another through no more than five people, we should consider these two people can become friends. Now, give you a tree of N people’s relationship. ( 1 <= N <= 1e5), you should compute the number of who can become friends of each people?  

v are acquainted with each other directly. People labels from 1.  

    In the next N lines, there is an integer in each line, indicates the number of people who can become the ith person’s friends. i is from 1 to n.  

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 const int MAXN = 1e5 + 5; 5  6 vector<int> vt[MAXN]; 7  8 int fa[MAXN][10];//u节点到达其孩子的距离为i的点的个数 9 int ch[MAXN][10];//u节点向上通过父节点到达的距离为i的点的个数10 11 void dfs(int u, int fa)12 {13     ch[u][0] = 1;14     if (vt[u].size() == 0) {15         return;16     }17     int i, j;18     int v;19     for (i = 0; i < vt[u].size(); ++i) {20         v = vt[u][i];21         if (v != fa) {22             dfs(v, u);23             for (j = 1; j <= 6; ++j) {24                 ch[u][j] += ch[v][j - 1];25             }26         }27     }28 }29 30 void dp(int u, int fa)31 {32     fa[u][0] = 1;33     int i;34 35     if (u != fa) {//非根节点36         fa[u][1] = 1;37         for (i = 2; i <= 6; ++i) {38             fa[u][i] = fa[fa][i - 1] + ch[fa][i - 1] - ch[u][i - 2];39         }40     }41     int v;42     for (i = 0; i < vt[u].size(); ++i) {43         v = vt[u][i];44         if (v != fa) {45             dp(v, u);46         }47     }48 }49 50 int main()51 {52     int T;53     int n;54     int u, v;55     int i, j;56     int cas = 0;57     int ans;58 59     scanf("%d", &T);60     while (T--) {61         scanf("%d", &n);62         for (i = 1; i <= n; ++i) {63             vt[i].clear();64         }65         memset(fa, 0, sizeof(fa[0]) * (n + 1));66         memset(ch, 0, sizeof(ch[0]) * (n + 1));67         for (i = 0; i < n - 1; ++i) {68             scanf("%d%d", &u, &v);69             vt[u].push_back(v);70             vt[v].push_back(u);71         }72         dfs(1, 1);73         dp(1, 1);74         printf("Case #%d:\n", ++cas);75 76 77         for (i = 1; i <= n; ++i) {78             ans = 0;79             for (j = 1; j <= 6; ++j) {80                 ans += fa[i][j] + ch[i][j];81             }82             printf("%d\n", ans);83         }84     }85 86     return 0;87 }