解题思路
-
核心思想:
- 使用DFS预处理每个节点的子树中红色节点数量
- 对于每次查询直接返回预处理的结果
-
实现步骤:
- 根据父节点数组构建树(邻接表)
- DFS遍历树,统计每个节点子树中的红色节点数
- 处理查询
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<int> g[N]; // 邻接表
int count_red[N]; // 每个节点子树中的红色节点数
string colors; // 节点颜色
int dfs(int u) {
int total = (colors[u-1] == 'R'); // 当前节点是否为红色
for(int v : g[u]) {
total += dfs(v);
}
return count_red[u] = total;
}
int main() {
int n;
cin >> n;
// 读入父节点数组并建图
for(int i = 2; i <= n; i++) {
int p;
cin >> p;
g[p].push_back(i);
}
// 读入颜色
cin >> colors;
// 预处理每个节点的子树红色节点数
dfs(1);
// 处理查询
int q;
cin >> q;
while(q--) {
int x;
cin >> x;
cout << count_red[x] << endl;
}
return 0;
}
import java.util.*;
public class Main {
static int N = 100010;
static ArrayList<Integer>[] g;
static int[] count;
static String colors;
static int dfs(int u) {
int total = (colors.charAt(u-1) == 'R' ? 1 : 0); // 当前节点是否为红色
for(int v : g[u]) {
total += dfs(v);
}
return count[u] = total;
}
@SuppressWarnings("unchecked")
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 初始化
g = new ArrayList[N];
for(int i = 0; i < N; i++) {
g[i] = new ArrayList<>();
}
count = new int[N];
// 读入父节点数组并建图
for(int i = 2; i <= n; i++) {
int p = sc.nextInt();
g[p].add(i);
}
// 读入颜色
colors = sc.next();
// 预处理每个节点的子树红色节点数
dfs(1);
// 处理查询
int q = sc.nextInt();
while(q-- > 0) {
int x = sc.nextInt();
System.out.println(count[x]);
}
sc.close();
}
}
import sys
sys.setrecursionlimit(100010)
def dfs(u, g, color, count):
"""统计以u为根的子树中红色节点数"""
total = 1 if color[u-1] == 'R' else 0 # 修正:索引从0开始
for v in g[u]:
total += dfs(v, g, color, count)
count[u] = total
return total
def main():
# 输入
n = int(input())
parents = [1] + list(map(int, input().split())) # 父节点数组
colors = input() # 节点颜色
# 建图(子节点表示)
g = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
g[parents[i-1]].append(i)
# 预处理每个节点的子树红色节点数
count = [0] * (n + 1)
dfs(1, g, colors, count)
# 处理查询
q = int(input())
for _ in range(q):
x = int(input())
print(count[x])
if __name__ == "__main__":
main()
算法及复杂度
- 算法:DFS预处理 + 在线查询
- 时间复杂度:
- 预处理:
- 每次查询:
- 总复杂度:
- 空间复杂度:,用于存储图和计数数组