题解 | #父子情深#

题意

一棵树节点初始权值为0，每次增加一个节点及其子树的权值，求最后每个节点的权值。

20分做法：暴力计算

直接按照题意暴力模拟，每次寻找要增加的节点及其子树。

80分做法：邻接矩阵+预处理

先用邻接矩阵把树变为方便处理的形式，再预处理节点和子树。
预处理找到所有子树的父节点，在操作时对于所有父节点的子节点加上相同的数，在q次操作完成之后，所有节点的权值都是其父节点与其自身的权值之和。

代码如下

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

class Solution {
public:
    vector<int> Map[100005];//存图数组
    int fa[100005];//存储祖先关系
    int N,Q;
    vector<Point> edge,query;
    vector<long> ans;
    inline void initialize()//初始化
    {
        for(int i=0;i<=N;i++)Map[i].clear();
        memset(fa,0,sizeof(fa));
        int p=edge.size();
        for(int i=0;i<p;i++) {Map[edge[i].x].push_back(edge[i].y);Map[edge[i].y].push_back(edge[i].x);}//存入树的边
    }
    void buildTree(int nodeNow)
    {
        int p=Map[nodeNow].size();
        for(int i=0;i<p;i++)
            if(Map[nodeNow][i]!=fa[nodeNow])
            {
                fa[Map[nodeNow][i]]=nodeNow;//寻找树的父节点
                buildTree(Map[nodeNow][i]);
            }
    }
    void nodeAdd(int nodeNow,int m)
    {
        ans[nodeNow-1]+=m;
        int p=Map[nodeNow].size();
        for(int i=0;i<p;i++)
            if(Map[nodeNow][i]!=fa[nodeNow])
            {
                nodeAdd(Map[nodeNow][i],m);//递归增加子树
            }
    }
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        N=n,Q=q,edge=Edge,query=Query;
        initialize();//初始化
        buildTree(1);//建树
        for(int i=0;i<q;i++) nodeAdd(query[i].x,query[i].y);//进行增加操作
    return ans;
    }
};

时间复杂度：，共处理q个点，每次循环n次。
空间复杂度：，共处理q个点，每处理一个点用去的栈空间。

100分做法：懒惰标记

懒惰标记是一种提升线段树时间复杂度的很有效的方法，我们可以把它的思想用于本题，在添加时，不直接添加，而是改为增加一个懒惰标记，最后一起处理，大大减少了时间复杂度。
代码如下

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

class Solution {
public:
    vector<int> Map[100005];
    int fa[100005];
    int N,Q;
    vector<Point> edge,query;
    vector<long> ans;
    inline void initialize()
    {
        for(int i=0;i<=N;i++)Map[i].clear();
        memset(fa,0,sizeof(fa));
        int p=edge.size();
        for(int i=0;i<p;i++) {Map[edge[i].x].push_back(edge[i].y);Map[edge[i].y].push_back(edge[i].x);}
        for(int i=0;i<Q;i++) fa[query[i].x]+=query[i].y;
    }
    int spread(int nodeNow,int nodePre,int ansSum)//将标记传播整个树
    {
        ansSum+=fa[nodeNow];//加上懒惰标记
        ans[nodeNow-1]=ansSum;
        int p=Map[nodeNow].size();
        for(int i=0;i<p;i++)
        if(Map[nodeNow][i]!=nodePre)spread(Map[nodeNow][i],nodeNow,ansSum);//将懒惰标记以当前节点传播
        return 0;
    }
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        N=n,Q=q,edge=Edge,query=Query;
        initialize();//初始化
        spread(1,0,0);
        return ans;
        //for(int i=0;i<5;i++) ans.push_back(fa[i]);
    }
};

时间复杂度：，全程只需处理一次，每个节点刚好到达一次。
空间复杂度：，共处理q个点，每处理一个点用去的栈空间。

样例解释


这两幅图表示了懒惰标记的传递过程，图1代表每个节点的懒惰标记值，图2表示每个节点的答案，注意到每个节点的答案都等于其所有祖先节点和其自身的懒惰标记数值之和。