题意：

给你一棵 $n$ 个节点的有根树，给你 $q$ 个操作，每次你需要将以 $u$ 为根节点的子树所有节点的权值加上 $v$

最后返回所有节点的权值

解法一（暴力算法，不可AC）

首先对整棵树进行一次dfs，预处理出每个节点的父节点

然后对于第 $i$ 个操作，我们直接一遍dfs将对应子树节点的权值加上对应的值

最后返回答案数组即可

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    vector<int> gr[100001];//邻接表存图
    vector<long> ans;//答案数组
    int fa[100001];//节点父节点数组
    void dfs_init(int u){//初始化预处理父节点
        for(auto v:gr[u]){
            if(v==fa[u])continue;
            fa[v]=u;
            dfs_init(v);
        }
    }
    void dfs_add(int u,int val){//将以u为根节点的子树节点的权值全部加上val
        ans[u-1]+=val;
        for(auto v:gr[u]){
            if(v==fa[u])continue;
            dfs_add(v,val);
        }
    }
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        for(int i=1;i<=n;i++){
            gr[i].clear();//多测清空
        }
        memset(fa,0,sizeof fa);//多测清空
        ans=vector<long>(n,0);
        for(auto e:Edge){
            gr[e.x].push_back(e.y);
            gr[e.y].push_back(e.x);
            //双向边
        }
        dfs_init(1);
        for(auto t:Query){
            dfs_add(t.x,t.y);
        }
        return ans;
    }
};

时间复杂度： $O(n*m)$ ，对于每一次操作的时间代价是 $O(n)$ 的，总共有 $m$ 次操作，故总的时间复杂度为 $O(n*m)$

空间复杂度： $O(n+m)$ ，存图、答案数组、父节点数组所占空间是 $O(n)$ 的，存操作的数组所占空间是 $O(m)$ 的，故总的空间复杂度为 $O(n+m)$

解法二（树上懒标记）

我们记 $tag[u]$ 表示以点 $u$ 为根节点的子树所加的权值和，每次操作我们只需要用 $O(1)$ 的时间

最后统计答案，我们可以以1为根节点对整棵树dfs，节点 $u$ 所对应的答案即为1节点到 $u$ 节点所经过路径的 $tag$ 值之和

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    vector<int> gr[100001];
    vector<long> ans;
    long tag[100001];
    void dfs(int u,int fa,long sum){
        //当前节点，父节点，当前的标记值之和
        sum+=tag[u];//加上当前节点的标记
        ans[u-1]=sum;//记录答案
        for(auto v:gr[u]){
            if(v==fa)continue;
            dfs(v,u,sum);
        }
    }
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        for(int i=1;i<=n;i++){
            gr[i].clear();//多测清空
        }
        ans=vector<long>(n,0);
        memset(tag,0,sizeof tag);//多测清空
        for(auto e:Edge){
            //连双向边
            gr[e.x].push_back(e.y);
            gr[e.y].push_back(e.x);
        }
        for(auto t:Query){
            tag[t.x]+=t.y;//添加懒标记
        }
        dfs(1,0,0);//从1号节点开始递归
        return ans;
    }
};

时间复杂度： $O(n+m)$ ，对整棵树dfs计算答案的时间复杂度为 $O(n)$ ，每次操作的时间复杂度为 $O(1)$ ，有 $m$ 次操作，故总的时间复杂度为 $O(n+m)$

空间复杂度： $O(n+m)$ ，存图、答案数组所占空间是 $O(n)$ 的，存操作的数组所占空间是 $O(m)$ 的，故总的空间复杂度为 $O(n+m)$

题解 | #父子情深#

题意：

解法一（暴力算法，不可AC）

解法二（树上懒标记）