开始时考虑的是暴力解法。构建树的过程就不说了。这里有一点需要注意，题目中的树并非二叉树，只是一个无环连通图，所以树节点中只能设定保存父节点的指针。在每次统计节点x的子节点中红色节点的个数时，使用一个辅助队列，开始时将x结点入队。进入循环后，查看队头结点是否为红色，然后遍历整棵树的所有结点，当遇到父节
展开全文
题目的主要信息：
没有回路的无向连通图，可以看成树，根结点为1
其中一部分结点染成了红色
之后有qqq次询问，每次询问以该结点作为根的子树有多少红色结点
具体做法：
根据输入的父节点，构建树的邻接表。
然后用字符串记录输入的染色信息，再通过dfs构建，对树进行染色，构建dp数组。其中dp[i]d
展开全文
解题思路
核心思想：
使用DFS预处理每个节点的子树中红色节点数量
对于每次查询直接返回预处理的结果
实现步骤：
根据父节点数组构建树（邻接表）
DFS遍历树，统计每个节点子树中的红色节点数
处理查询
代码
cpp
java
python
#include &l
展开全文
题目的输入用的节点，目标是遍历节点，所以链表用邻接表（拉链表）存储带缓存的递归循环法性能差别还蛮明显的
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int
展开全文
dp[i]:以第i个节点为根节点的子树的染色个数。
tree[i]:为第i个节点的父亲节点。
先获取树，然后为需要染色的节点赋值dp[i]=1，最后从第n个节点依次往前逐次把dp[i]增加到dp[tree[i]]上。
dp[tree[i]]+=dp[i];
#include<iostream&
展开全文
# include <stdio.h>
# include <string.h>
# include <limits.h>
int max(int a,int b){
return a>b?a:b;
}
int mai
展开全文
#include <iostream>
using namespace std;
struct ChildNode
{
int child;
struct ChildNode *next;
};
struct ParentNode
{
int i;
展开全文
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br =
展开全文
n = int(input())
parents = list(map(int, input().split()))
# 树的表示
tree = [[] for _ in range(n+1)]
for i, p in enumerate(parents):
i = i + 2
tr
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
