题目内容

塔子哥是一名计算机科学家，他正在研究一种新的数据结构——树。树是一种无向无环联通图，它由若干个节点和若干条边组成。

每个节点都可以有0,1,2个子节点，而每条边都连接两个节点。塔子哥现在有一棵树，树上的每个节点都有自己的价值。价值的计算规则如下所示：

思路:树上dfs

题目保证这是一棵有根树，且每个节点的子节点最多 $2$ 个。所以可以考虑自底向上(也就是从各个叶子节点开始)dfs，根据题目意思求解每个点的权值。

时间复杂度：$O(n)$

类似知识点题目推荐

这道题是非常经典，也非常"裸"的树上dfs问题。LeetCode上有非常多的例题，并且在2023年春招过程中考了114514次。望周知。

LeetCode

1. 112. 路径总和
2. 129. 求根到叶子节点数字之和
3. 236. 二叉树的最近公共祖先

CodeFun2000

1.P1224 携程 2023.04.15-春招-第三题-魔法之树

2.P1159. 2022年清华大学(深圳)保研夏令营机试题-第一题-树上计数

3.P1196 华为 2023-04-19-第二题-塔子哥出城

4.P1044. 拼多多内推笔试-2023.2.22.投喂珍珠

5.P1193. 腾讯音乐 2023.04.13-暑期实习-第二题-价值二叉树

更多请见:知识点分类-训练-深度优先搜索专栏

代码

C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> c(n);
    vector<vector<int>> g(n);
    // 读入数据
    for (int i = 1; i < n; ++i) {
        int fa; cin >> fa;
        g[fa - 1].emplace_back(i);
    }
    for (int i = 0; i < n; ++i) cin >> c[i];
    // C++11 的Lambda表达式 , dfs
    function<int(int)> dfs = [&](int u) {
        // 遇到叶子节点 = 递归出口，向上返回
        if (g[u].empty()) return 1;
        // 先递归求儿子节点的权值，然后根据题意求该节点的权值
        int sum = 0;
        for (int v: g[u]) {
            if (c[u] == 1) sum += dfs(v);
            else sum ^= dfs(v);
        }
        return sum;
    };

    cout << dfs(0) << "\n";

    return 0;
}

Java

import java.util.*;
import java.util.function.*;

public class Main {

    private static List<Integer> c; // 标记每个节点的颜色
    private static List<List<Integer>> g; // 存储树的邻接表
    private static int dfs(int u) {
        // 遇到叶子节点，返回
        if (g.get(u).isEmpty()) return 1; 
        int sum = 0;
        for (int v : g.get(u)) {  // 遍历当前节点的邻居节点
            if (c.get(u) == 1) sum += dfs(v); // 当节点的颜色为红色时，将其子节点的dfs和加起来
            else sum ^= dfs(v); // 当节点的颜色为绿色时，将其子节点的dfs和异或起来
        }
        return sum; // 返回最终计算得到的值
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 读入节点数

        c = new ArrayList<>(); // 初始化颜色列表
        g = new ArrayList<>(); // 初始化邻接表

        for (int i = 0; i < n; ++i) {
            g.add(new ArrayList<>()); // 为每一个节点创建一个空的邻接表
        }

        for (int i = 1; i < n; ++i) {
            int fa = scanner.nextInt(); // 读入当前节点的父节点
            g.get(fa - 1).add(i); // 将当前节点加入父节点的邻接表
        }

        for (int i = 0; i < n; ++i) {
            c.add(scanner.nextInt()); // 读入每个节点的颜色
        }

        System.out.println(dfs(0)); // 输出从根节点开始的深度优先搜索结果
    }
}

Python

n = int(input())  # 读入节点数

g = [[] for i in range(n)]  # 初始化邻接表

fa = list(map(int, input().split(" ")))  # 读入每个节点的父节点
for i in range(0, n - 1):
    g[fa[i] - 1].append(i + 1)  # 将当前节点加入父节点的邻接表

c = list(map(int, input().split(" ")))  # 读入每个节点的颜色


def dfs(u):
    if len(g[u]) == 0:
        return 1  # 叶子节点，默认返回1
    s = 0
    for v in g[u]:  # 遍历当前节点的邻居节点
        if c[u] == 1: s += dfs(v)  # 当节点的颜色为白色时，将其子节点的dfs和加起来
        else: s ^= dfs(v)  # 当节点的颜色为黑色时，将其子节点的dfs和异或起来
    return s  # 返回最终计算得到的值


print(dfs(0))  # 输出从根节点开始的深度优先搜索结果

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    let n = parseInt(lines[0]);  // 读入节点数
    let g = new Array(n);
    for(let i=0; i<n; i++) {
        g[i] = new Array();
    }  // 初始化邻接表
    let fa = lines[1].split(" ").map(Number);
    for(let i=0; i<n-1; i++) {
        g[fa[i]-1].push(i+1);  // 将当前节点加入父节点的邻接表
    }  // 读入每个节点的父节点

    let c = lines[2].split(" ").map(Number);  // 读入每个节点的颜色

    function dfs(u) {
        if(g[u].length === 0) {
            return 1;
        }  // 叶子节点默认返回1
        let s = 0;
        g[u].forEach((v) => {
            if(c[u] === 1) s += dfs(v);  // 当节点的颜色为白色时，将其子节点的dfs和加起来
            else s ^= dfs(v);  // 当节点的颜色为黑色时，将其子节点的dfs和异或起来
        });
        return s;  // 返回最终计算得到的值
    }

    console.log(dfs(0));  // 输出从根节点开始的深度优先搜索结果
});

Go

package main

import (
    "fmt"
)

func dfs(u int, g [][]int, c []int) int {
    if len(g[u]) == 0 {
        return 1    // 叶子节点，默认返回1
    }
    s := 0
    for _, v := range g[u] {    // 遍历当前节点的邻居节点
        if c[u] == 1 {
            s += dfs(v, g, c)   // 当节点的颜色为白色时，将其子节点的dfs和加起来
        } else {
            s ^= dfs(v, g, c)   // 当节点的颜色为黑色时，将其子节点的dfs和异或起来
        }
    }
    return s    // 返回最终计算得到的值
}

func main() {
    var n int
    fmt.Scan(&n)    // 读入节点数

    g := make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, 0)
    }    // 初始化邻接表

    fa := make([]int, n-1)
    for i := 0; i < n-1; i++ {
        fmt.Scan(&fa[i])
        g[fa[i]-1] = append(g[fa[i]-1], i+1)    // 将当前节点加入父节点的邻接表
    }    // 读入每个节点的父节点

    c := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&c[i])
    }    // 读入每个节点的颜色

    fmt.Println(dfs(0, g, c))    // 输出从根节点开始的深度优先搜索结果
}