奖金（改错）

· · 个人记录

奖金(bonus)

【题目描述】

巨硬公司是微软公司的竞争对手，今年为了鼓励员工们的积极性决定发放 q 次奖金，奖金的发放是以 部门领导为单位，巨硬公司的体系为一个领导和若干的该领导的下属，而其下属也可以是其他员工的领导。 巨硬公司的董事会决定，每次选定一个编号为 i 的领导（已知该公司最大领导的编号为 1 ），给领导 及其全部下属发放奖金。

问经过 q 次发放后，每个员工（包含领导）最终能够获得多少万的奖励。

【输入格式】

第一行两个数 n 和 q，表示员工总数，q表示发放q次奖金。

接下来n行每行两个正整数 x 和 y，表示 x 和 y 之间存在工作上的上下级关系，但x和y可能x是y的上级，也 可能y是x的上级。

再接下里q行每行两个正整数 id 和 f ，表示给编号为 id 的员工及其全部下属每人发放 f 万的奖金。

【输出格式】

输出n个数据，以空格隔开，代表的是从编号 1 至 n 个领导获得奖金的总数

【数据范围与约定】

对于50%的数据，1<=n,q<=2000

对于另外10%的数据，有y=x+1

对于100%的数据，1<=n,q<=2*10^5,0<=f<=10^4

代码实现：

#include<bits/stdc++.h>
using namespace std;
int father[1000005],sum[1000005];
vector<int> e[1000005];
void FindFather(int s=1,int f=0){       //寻找父亲 s表示编号,f表示此节点父亲（领导）
    father[s]=f;
    for(int i=0;i<e[s].size();i++){
        int c=e[s][i];
        if(c==f){
            continue;
        }
        FindFather(c,s);
    }
}
void GetAns(int s=1,int b=0){
    sum[s]+=b;
    for(int i=0;i<e[s].size();i++){     //循环存储该节点奖金值
        int c=e[s][i];
        if(c==father[s]){
            continue;
        }
        GetAns(c,sum[s]);
    }
}
int main(){
    freopen("bonus.in","r", stdin);     //注意文件操作
    freopen("bonus.out","w", stdout);
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0;i<n-1;i++){             //n个节点一共n-1条边 
        int a,b;
        scanf("%d%d",&a,&b);
        e[a].push_back(b);              //无向存边
        e[b].push_back(a);
    }
    FindFather();
    for(int i=0;i<q;i++){
        int id,f;
        scanf("%d%d",&id,&f);           //id表示节点编号，f表示奖金
        sum[id]+=f;
    }
    GetAns();
    for(int i=1;i<=n;i++){
        printf("%d ",sum[i]);
    }
    return 0;
}