题解 | #父子情深#

题意整理

给定一颗有n个节点的树，每个节点权值初始为0。
现在有一个查询集合，集合中每一项提供两个参数r和v，每次查询将r节点及其子节点的权值增加v。
返回最终每个节点的权值。

方法一（DFS）

1.解题思路

首先建立邻接表，用于访问某个节点的所有子节点。
初始化查询中当前根节点的权值。
按照建立的邻接表，递归地遍历当前根节点下每个子节点，如果没有访问过，则加上对应权值。按照这个规则访问完所有的节点。

由于测试数据较大，运行报栈深度溢出（StackOverflowError）。可以通过自定义栈深度，防溢出。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 从 1 到 n 每个结点的权值。
     * @param n int 
     * @param Edge Point一维数组 (u, v) 集合
     * @param q int 
     * @param Query Point一维数组 Point.x 为题中 r, Point.y为题中 v
     * @return long一维数组
     */
    //节点个数
    int n;
    //标记数组
    boolean[] v;
    //邻接表
    List<List<Integer>> graph;
    //权值数组
    long[] w;

    public long[] solve (int n, Point[] Edge, int q, Point[] Query) {
        //初始化
        this.n=n;
        this.v=new boolean[n];
        this.graph=new ArrayList<>();

        //给邻接表赋值
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(Point point:Edge){
            int u=point.x;
            int v=point.y;
            graph.get(u-1).add(v-1);
            graph.get(v-1).add(u-1);
        }

        //给权值数组赋值
        this.w=new long[n];
        for(int i=0;i<q;i++){
            w[Query[i].x-1]+=Query[i].y;
        }

        //从根节点开始，给每一个子节点增加权值
        v[0]=true;

        try{
            Thread t=new Thread(null,()->{
                dfs(0);
            },"自定义栈深度",1<<30);
            t.start();
            t.join();
        }
        catch(Exception e){

        }

        return w;
    }

    //递归地给子节点增加权值
    private void dfs(int i){
        for(Integer j:graph.get(i)){
            //如果子节点没被访问到，则增加对应权值
            if(!v[j]){
                w[j]+=w[i];
                v[j]=true;
                dfs(j);
            }
        }
    }

}

3.复杂度分析

时间复杂度：最坏情况下，需要访问所有的节点，所以时间复杂度为 $O(n)$ 。
空间复杂度：最坏情况下，需要额外深度为n的递归栈、大小为n的标记数组以及大小为 $n^2$ 的邻接表，所以空间复杂度为 $O(n^2)$ 。

方法二（BFS）

1.解题思路

首先建立邻接表，用于访问某个节点的所有子节点。
初始化查询中当前根节点的权值。
将根节点入队，遍历当前根节点的所有子节点，如果未被访问过，则增加对应权值，同时将该节点入队，继续遍历。

动图展示：
图片说明

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 从 1 到 n 每个结点的权值。
     * @param n int 
     * @param Edge Point一维数组 (u, v) 集合
     * @param q int 
     * @param Query Point一维数组 Point.x 为题中 r, Point.y为题中 v
     * @return long一维数组
     */
    //节点个数
    int n;
    //标记数组
    boolean[] v;
    //邻接表
    List<List<Integer>> graph;
    //权值数组
    long[] w;

    public long[] solve (int n, Point[] Edge, int q, Point[] Query) {
        //初始化
        this.n=n;
        this.v=new boolean[n];
        this.graph=new ArrayList<>();

        //给邻接表赋值
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(Point point:Edge){
            int u=point.x;
            int v=point.y;
            graph.get(u-1).add(v-1);
            graph.get(v-1).add(u-1);
        }

        //给权值数组赋值
        this.w=new long[n];
        for(int i=0;i<q;i++){
            w[Query[i].x-1]+=Query[i].y;
        }

        //初始化队列
        Queue<Integer> queue=new LinkedList<>();
        //将根节点添加到队列
        v[0]=true;
        queue.offer(0);

        while(!queue.isEmpty()){
            int i=queue.poll();
            //遍历当前根节点所有子节点
            for(Integer j:graph.get(i)){
                //如果未被访问过，则增加对应权值
                if(!v[j]){
                    w[j]+=w[i];
                    v[j]=true;
                    queue.offer(j);
                }
            }
        }
        return w;
    }

}

3.复杂度分析

时间复杂度：最多访问n个节点，所以时间复杂度为 $O(n)$ 。
空间复杂度：最坏情况下，需要额外大小为n的队列、大小为n的标记数组以及大小为 $n^2$ 的邻接表，所以空间复杂度为 $O(n^2)$ 。