树(tree)

【题目描述】

从前在森林里面有一棵很大的树，树上住着很多小动物。

树上有?个房间，第?个房间都住着??只第??种小动物。

这?个房间用? − 1条路径连接起来，其中节点1为整棵树的根。

现在每个房间?的小动物们都想知道，以?为根的子树中有多少只他们的同

类？

【输入格式】

第一行一个整数?表示房间数。

之后?行，每行两个数，表示??, ??。

再之后? − 1行，每行两个数?, ?，表示树上有一条连接?, ?的边。

【输出格式】

一行，?个数，第?个数表示以?为根的子树中??种小动物有多少只。

【样例输入】

5

2 1

3 1

4 2

5 1

6 2

1 2

1 3

3 4

3 5

【样例输出】

10 3 10 5 6

【数据规模与约定】

对于30%的数据，?? ≤ ? ≤ 10

对于60%的数据，?? ≤ ? ≤ 1000

对于100%的数据，?? ≤ ? ≤ 100000, ?? ≤ 1000

 

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 100000using namespace std;vector
           
            vec[N];int n,a[N],b[N],ans[N];int f[N],dad[N],x,y;void dfs(int x){ ans[x]=f[b[x]]; f[b[x]]+=a[x]; for(int i=0;i