164、生物家族能量查询.docx

解题思路

问题分析

探险者希望查询某个生物以及其所有子孙的能量值总和。在这样的场景下，由于我们需要快速查询一个节点的所有子孙，我们需要某种方法来轻松地找到一个节点的所有子孙。在这里，我们可以引入一个重要的数据结构技术：DFS序。

方法引入

DFS序是通过深度优先遍历树来得到的节点序列。在DFS过程中，每个节点被访问两次，一次是首次访问，另一次是从子节点返回时。记录下这些事件，我们可以得到一个序列。

通过DFS序，我们可以将节点及其所有子孙在原树中的结构转化为序列上的一个连续的范围。这样，问题就变成了查询一个连续区间的和，这个问题可以通过前缀和、线段树或树状数组轻松解决。

方法实现

DFS遍历：从根节点开始进行深度优先遍历，并为每个节点分配一个连续的编号。同时，记录每个节点在DFS序列中的开始和结束位置。

前缀和：建立一个前缀和数组，使得我们能在O(1)?时间内查询任意连续区间的和。

查询：对于每次查询，找到该节点在DFS序列中的开始和结束位置，通过前缀和数组查询得到答案。

方法优劣分析

优点：方法的主要优点是查询速度快，只需要?O(1)?的时间。同时，空间需求也相对较低，只需要存储DFS序列和前缀和数组。

缺点：预处理阶段需要?O(n)?的时间来完成DFS遍历和前缀和数组的计算。

时间复杂度分析：预处理阶段：O(n)。查询阶段：O(1)。总时间复杂度：O(n+q)。

空间复杂度分析：存储DFS序列和前缀和数组，需要O(n)?的空间。

AC_Code

C++

#includeiostream

#includevector

usingnamespacestd;

#definelllonglong

constintMAXN=1e5+5;

vectorinttree[MAXN];//树的邻接表表示

llenergy[MAXN];//每个生物的能量

llprefix_sum[MAXN*2];//前缀和数组

lldfs_in[MAXN];//每个节点在DFS序列中的开始位置

lldfs_out[MAXN];//每个节点在DFS序列中的结束位置

lldfs_clock=0;//DFS序的时钟

boolisRoot[MAXN];//标记每个节点是否可能是根

//深度优先遍历来记录DFS序

voiddfs(intu){

dfs_in[u]=++dfs_clock;

prefix_sum[dfs_clock]=energy[u];

for(intv:tree[u]){

dfs(v);

}

dfs_out[u]=++dfs_clock;

}

intmain(){

intn;

cinn;

for(inti=1;i=n;++i){

cinenergy[i];

isRoot[i]=true;//初始化每个节点都可能是根

}

for(inti=0;in-1;++i){

intu,v;

cinuv;

tree[u].push_back(v);//添加到树中

isRoot[v]=false;//v不是根，因为它是u的子孙

}

introot=1;

for(inti=1;i=n;++i){

if(isRoot[i]){

root=i;

break;

}

}

dfs(root);//使用确定的根节点

//构建前缀和数组

for(inti=1;i=2*n;++i){

prefix_sum[i]+=prefix_sum[i-1];

}

intq;

cinq;

while(q--){

intx;

cinx;

//使用前缀和数组查询结果

coutprefix_sum[dfs_out[x]]-prefix_sum[dfs_in[x]-1]endl;

}

return0;

}

Java

importjava