题目描述
在一颗有 n 个结点且以 1 为根节点树上，起初每个结点的初始权值为 0 。
现在有 q 次操作，每次操作选择将以 为根节点的子树上的所有结点权值增加
。
求 q 次操作后从 1 到 n 每个结点的权值。
输入:
第一个参数为 n，1≤n≤100,000
第二个参数为边 的集合，其中
表示结点
与结点
之间有一条边，1≤ui,vi≤n
第三个参数为 q，1≤q≤100,000
第四个参数为 q 次询问的 的集合，1≤ri≤n,0≤∣vi∣≤1000,000
返回:
从 1 到 n 每个结点的权值。
示例1
输入：5,[(2,5),(5,3),(5,4),(5,1)],2,[(1, 3), (2, -1)]
返回值：[3,2,3,3,3]
说明：
第一次操作，将以 1 为根节点的子树上的所有结点权值增加 3，此时结点的权值分别为 [3, 3, 3, 3, 3] ；
第二次操作，将以 2 为根节点的子树上的所有结点权值增加 -1，此时结点的权值分别为 [3, 2, 3, 3, 3] ；
题目分析
题目的结点值是从1~n，一共n个结点，组成一棵树，树有n-1条边，Edge数组记录边的两个结点，在此题中可以使用邻接表的方式记录父节点和子节点的关系；
邻接表主要是对每个结点都创建一个存储相邻的结点的列表，在列表中会重复记录父节点，所以需要一个访问数组 visited 来标记结点是否已经被访问过，第一次遇到说明是父节点，会继续遍历它的邻接表，后面再次遇到说明是子节点的邻接点，可以跳过；
具体遍历过程如下：
解题思路
方法1：DFS遍历整个树，获取每个结点权值
dfs的思路比较直观：
1.创建邻接表graph，根据Edge数组初始化邻接表，对于权值操作，创建权值数组res，可以直接在每个结点上统一计算变化值，然后子节点的变化值是继承父节点的，初始值为0，则只要不断加上父节点的值即可 res[child] += res[parent]；
2.创建访问数组 visited 来标记结点是否已经访问过；
3.dfs从根开始遍历，访问根的子节点（邻接表），直到全部都访问过，返回结果值res；
方法2：BFS遍历整个树，获取每个结点权值
dfs遍历会需要较多的栈空间，一旦超过设定的栈深度，就会报栈溢出错误，使用bfs可以避免；
bfs遍历树，一般借助队列来实现，bfs的模板如下：
bfs(root){
Queue queue;
queue.offer(根节点);
while(队列不为空){
// 取出根节点
TreeNode node = queue.poll();
// 遍历根节点的子节点，并加入队列中
for(TreeNode child : node的邻接表){
queue.offer(child);
}
}
}代码实现
方法1：DFS（会报栈溢出错误）
// 判断结点是否访问过
boolean[] visited;
// 结果数组
long[] res;
// 创建邻接表（每个结点对应相连的结点列表（连线的两个端点都有））
List<List<Integer>> graph;
public long[] solve (int n, Point[] Edge, int q, Point[] Query) {
// 判断边数组是否访问过
visited = new boolean[n];
// 结果数组
res = new long[n];
// 初始化邻接表
graph = new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
for(int i=0;i<Edge.length;i++){
int u = Edge[i].x;
int v = Edge[i].y;
// u,v值对应的下标都需要减1，连线的两端点的邻接表都要增加
graph.get(u-1).add(v-1);
graph.get(v-1).add(u-1);
}
// 给结果数组赋权值，表示每个值上需要增加的值（默认为0）
for(int i=0;i<q;i++){
res[Query[i].x -1] += Query[i].y;
}
// 从根节点开始增加权值
visited[0] = true;
// dfs
dfs(0);
return res;
}
public void dfs(int i){
// 遍历邻接表
List<Integer> next = graph.get(i);
for(Integer nx : next){
// 子节点未访问过，需要增加权值
if(!visited[nx]){
res[nx] += res[i];
visited[nx] = true;
// 继续遍历子节点的邻接表
dfs(nx);
}
}
}时间复杂度：，首先需要创建长度为n的邻接表，同时也要遍历Edge和Query数组，在dfs的过程中，在每个结点都只有一个子节点的情况下，递归深度达到最大n，所以花费的总时间为 n+e+q+n，还是n级别；
空间复杂度：，空间上需要2(n-1)来存邻接结点（n个结点的树有n-1条边，边上的两个结点都会在邻接表中重复出现，所以是2(n-1)），还需要深度最大为n的递归栈空间，因为栈深度的限制，使用dfs时会报栈溢出错误；
方法2：BFS（借助队列，避免栈溢出）
// 判断结点是否访问过
boolean[] visited;
// 结果数组
long[] res;
// 创建邻接表（每个结点对应相连的结点列表（连线的两个端点都有））
List<List<Integer>> graph;
public long[] solve (int n, Point[] Edge, int q, Point[] Query) {
// 判断边数组是否访问过
visited = new boolean[n];
// 结果数组
res = new long[n];
// 初始化邻接表
graph = new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
for(int i=0;i<Edge.length;i++){
int u = Edge[i].x;
int v = Edge[i].y;
// u,v值对应的下标都需要减1，连线的两端点的邻接表都要增加
graph.get(u-1).add(v-1);
graph.get(v-1).add(u-1);
}
// 给结果数组赋权值，表示每个值上需要增加的值（默认为0）
for(int i=0;i<q;i++){
res[Query[i].x -1] += Query[i].y;
}
// 从根节点开始增加权值
visited[0] = true;
// 借助队列进行DFS遍历
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
while(!queue.isEmpty()){
int root = queue.poll();
// 访问邻接节点
for(Integer nx : graph.get(root)){
// 子节点未访问过，需要增加权值
if(!visited[nx]){
res[nx] += res[root];
visited[nx] = true;
// 继续遍历子节点的邻接表
queue.offer(nx);
}
}
}
return res;
}时间复杂度：，与dfs类似需要遍历数组，bfs使用的队列，省掉了递归的栈时间，增加了遍历邻接表的时间，时间复杂度为n级别；
空间复杂度：，与dfs相似，减少了栈空间，增加了队列来存储结点值，空间复杂度级别为n。
京公网安备 11010502036488号