java 牛客网之[动态规划 中等]NC15 小红的树

java 牛客网之[动态规划 中等]NC15 小红的树

题目的链接在这里：https://www.nowcoder.com/practice/66ab364d3fba487eb39bd3460fd484c0

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • 树形dp

---

题目大意 小红拿到了一棵有根树。根节点为1号节点。 所谓树，指没有回路的无向连通图。 现在小红想给一部分点染成红色。之后她有 次询问，每次询问某点的子树红色节点的个数。

---

一、示意图

二、解题思路

树形dp

树形dp

代码如下：

import java.util.*;

public class  Main{
    
    static int[] dp;
    static String str;
    static ArrayList> graph;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //+10可能就是为了把范围扩大
        dp=new int[n+10];
        graph=new ArrayList<>(n+10);
        //然后开始初始化
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<>());
        }
        //然后是p n-1个整数 代表第2个节点到第n个节点的父亲
        for(int i=2;i<=n;i++){
            int p=sc.nextInt();
            //p就是对应节点的父亲 表示就是p这个位置的子节点是i
            graph.get(p).add(i);
        }

        //然后是 RW这些数值 next和nextLine的区别
        str=sc.next();
        //然后开始递归
        DFS(1,-1);
        //然后这就更新结束了
        int q=sc.nextInt();
        while (q-->0){
            //那就开始判断
            int x=sc.nextInt();
            System.out.println(dp[x]);
        }
    }

    private static int DFS(int x, int p) {
        //目的是求一个x子树的红色节点 那就是说dp[i]表示的就是 i的子树红色节点数量 p表示的是父节点？
        int sum=0;
        //先判断这个节点是不是红色的
        if(str.charAt(x-1)=='R'){
            sum++;
        }
        //然后再判断x的子节点
        for(int i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5160643.html