【牛客编程巅峰赛S1第3场】父子情深

题目

在一颗有 个结点且以 1 为根节点树上，起初每个结点的初始权值为 0。
现在有 次操作，每次操作选择将以 为根节点的子树上的所有结点权值增加 。
求 次操作后从 1 到 每个结点的权值。

输入
第一个参数为 n，
第二个参数为边 的集合，其中 表示结点 与结点 之间有一条边，
第三个参数为 ，
第四个参数为 次询问的 的集合，

返回
从 1 到 每个结点的权值。

解题思路

使用 DFS 算法

记录与某个点相邻的所有点。 记录从 1 到 n 每个结点的权值。 一开始记录的是每个节点增加的权值，而不考虑节点的子树。

函数计算最终每个节点的权值。
从根节点 1 开始，深度优先遍历整个树。使用 记录点是否是遍历过，以区分是节点是子节点还是父节点。
如果是子节点，那么将该节点的权值加到子节点权值中，直到叶子节点结束。

C++代码

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
    vector<vector<int>> next;
    vector<int> vis;
    vector<long> weight;

    void dfs(int x){
        for(int i=0; i<next[x].size(); ++i){
            int e = next[x][i];
            if(!vis[e]){
                weight[e-1] += weight[x-1];
                vis[e] = true;
                dfs(e);
            }
        }
    }
public:
    /**
     * 从 1 到 n 每个结点的权值。
     * @param n int整型 
     * @param Edge Point类vector (u, v) 集合
     * @param q int整型 
     * @param Query Point类vector Point.x 为题中 r, Point.y为题中 v
     * @return long长整型vector
     */
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        // write code here
        next.resize(n+1);
        for(int i=0; i<Edge.size(); ++i){
            int u = Edge[i].x;
            int v = Edge[i].y;
            next[u].push_back(v);
            next[v].push_back(u);
        }
        weight.resize(n, 0);
        for(int i=0; i<q; ++i){
            int r = Query[i].x;
            int v = Query[i].y;
            weight[r-1] += v;
        }
        vis.resize(n+1, false);
        vis[1] = true;
        dfs(1);
        return weight;
    }
};