题解 | #扩散II#

扩散II

http://www.nowcoder.com/practice/81e787ebf9644250b0977e344991aeb1

题意：

        有一颗节点为 n 的树，初始时每个节点的值都是0。
      现有 m 次操作，每次操选定一个节点 $x_{i}$ ，使得与节点 $x_{i}$ 相邻距离小于等于 $y_{i}$ 的节点的值都加 $z_{i}$ 。

      问最后每个节点的值为多少？

方法一：

dfs

思路：

外层循环是操作次数 m 。

对每次操作都从节点x开始 dfs ，距离不超过 y ,遍历的符合条件节点的值都加 z 。

class Solution {
public:
    
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x, vector<int>& y, vector<int>& z) {
        vector<int> sum(n+1,0);//存储每个节点的值
        vector<int> vis(n+1,0);
        vector<vector<int>> g(n+1);//建树
        
        for(int i=0;i<n-1;i++){
            g[u[i]].push_back(v[i]);
            g[v[i]].push_back(u[i]);
        }
        
        for(int i=0;i<m;i++){
            sum[x[i]]+=z[i];
            vis[x[i]]=1;
            dfs(g,sum,vis,x[i],y[i],z[i]);//对每次操作都从该节点开始dfs
            vis[x[i]]=0;
        }
        sum.erase(sum.begin());//返回下标从1开始的数组
        return sum;
    }
    
    void dfs(vector<vector<int>> g,vector<int>& sum,vector<int> vis,int x,int y,int z){
        if(y==0){//当距离==0，return
            return;
        }
        
        int num=g[x].size();
        for(int i=0;i<num;i++){//遍历
            int t=g[x][i];
            if(vis[t]==0){//未访问过，则访问
                vis[t]=1;
                sum[t]+=z;
                dfs(g,sum,vis,t,y-1,z);
                vis[t]=0;
            }
        }
    }
};

时间复杂度： $O(m*n),m是外层的污染次数，n是最坏情况每次都访问全部节点。$

空间复杂度： $O(n^{2}),n是节点个数，树的存储，vis[],sum[]$

方法二：

bfs

思路：

同方法一思路一样。

     外层循环是操作次数 m 。

对每次操作都从节点x开始 bfs ，距离不超过 y ,遍历的符合条件节点的值都加 z 。

一次bfs操作的过程如下所示：

操作过程如下：

class Solution {
public:
    
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x, vector<int>& y, vector<int>& z) {
        vector<int> sum(n+1,0);//存储每个节点的值
        vector<int> vis(n+1,0);
        vector<vector<int>> g(n+1);//建树
        
        for(int i=0;i<n-1;i++){
            g[u[i]].push_back(v[i]);
            g[v[i]].push_back(u[i]);
        }
        
        for(int i=0;i<m;i++){//对每次操作都从该节点开始bfs
            bfs(g,sum,vis,x[i],y[i],z[i]);
        }
        sum.erase(sum.begin());//返回下标从1开始的数组
        return sum;
    }
    
    void bfs(vector<vector<int>> g,vector<int>& sum,vector<int> vis,int x,int y,int z){
        queue<pair<int,int>> q;
        q.push({x,0});//入队
        sum[x]+=z;
        vis[x]=1;
        while(!q.empty()){
            auto now=q.front();
            q.pop();
            int u=now.first,step=now.second; 
            int num=g[u].size();
            for(int i=0;i<num;i++){
                int v=g[u][i];
                    if(vis[v]==0&&step+1<=y){//未访问过并且距离<=y，则访问
                        vis[v]=1;//设置为已访问
                        sum[v]+=z;
                        q.push({v,step+1});//入队列
                    }
            }
        }
            
    }
};