package main

import (
	"fmt"
	"maps"
)

func goodSubtreeSum(vals, par []int) (ans int) {
	const mod = 1_000_000_007
	const D = 10
	n := len(par)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		p := par[i]
		g[p] = append(g[p], i)
	}

	type pair struct{ mask, val int }
	var dfs func(int) (map[int]int, []pair)
	dfs = func(x int) (f map[int]int, single []pair) {
		f = map[int]int{}

		// 計算 val 的數位集合 mask
		val := vals[x]
		mask := 0
		for v := val; v > 0; v /= D {
			d := v % D
			if mask>>d&1 > 0 {
				mask = 0
				break
			}
			mask |= 1 << d
		}

		if mask > 0 {
			f[mask] = val
			single = append(single, pair{mask, val})
		}

		for _, y := range g[x] {
			fy, singleY := dfs(y)

			// 啓發式合併
			if len(singleY) > len(single) {
				single, singleY = singleY, single
				f, fy = fy, f
			}

			single = append(single, singleY...)

			// 把子樹 y 中的 mask 和 val 一個一個地加到 f 中
			for _, p := range singleY {
				msk, v := p.mask, p.val
				if v <= f[msk] {
					continue
				}
				nf := maps.Clone(f)
				nf[msk] = v
				for msk2, s2 := range f {
					if msk&msk2 == 0 {
						nf[msk|msk2] = max(nf[msk|msk2], v+s2)
					}
				}
				f = nf
			}
		}

		mx := 0
		for _, s := range f {
			mx = max(mx, s)
		}
		ans += mx

		return
	}
	dfs(0)
	return ans % mod
}

func main() {
	vals := []int{3, 22, 5}
	par := []int{-1, 0, 1}
	result := goodSubtreeSum(vals, par)
	fmt.Println(result)
}

# -*-coding:utf-8-*-

from typing import List, Dict, Tuple
import copy

def goodSubtreeSum(vals: List[int], par: List[int]) -> int:
    mod = 1_000_000_007
    D = 10
    n = len(par)
    
    # 構建樹結構
    g = [[] for _ in range(n)]
    for i in range(1, n):
        p = par[i]
        g[p].append(i)
    
    ans = 0
    
    def dfs(x: int) -> Tuple[Dict[int, int], List[Tuple[int, int]]]:
        nonlocal ans
        f = {}
        
        # 計算 val 的數位集合 mask
        val = vals[x]
        mask = 0
        v = val
        valid_mask = True
        
        while v > 0:
            d = v % D
            if mask >> d & 1:
                valid_mask = False
                break
            mask |= 1 << d
            v //= D
        
        single = []
        if valid_mask and mask > 0:
            f[mask] = val
            single.append((mask, val))
        
        for y in g[x]:
            fy, singleY = dfs(y)
            
            # 啓發式合併：確保 single 是較大的那個
            if len(singleY) > len(single):
                single, singleY = singleY, single
                f, fy = fy, f
            
            single.extend(singleY)
            
            # 把子樹 y 中的 mask 和 val 一個一個地加到 f 中
            for msk, v in singleY:
                if v <= f.get(msk, 0):
                    continue
                    
                nf = copy.deepcopy(f)
                nf[msk] = v
                
                for msk2, s2 in f.items():
                    if msk & msk2 == 0:
                        combined_mask = msk | msk2
                        nf[combined_mask] = max(nf.get(combined_mask, 0), v + s2)
                
                f = nf
        
        # 更新答案
        mx = 0
        for s in f.values():
            mx = max(mx, s)
        ans += mx
        
        return f, single
    
    dfs(0)
    return ans % mod

def main():
    vals = [3, 22, 5]
    par = [-1, 0, 1]
    result = goodSubtreeSum(vals, par)
    print(result)

if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <functional>

using namespace std;

int goodSubtreeSum(vector<int>& vals, vector<int>& par) {
    const int mod = 1000000007;
    const int D = 10;
    int n = par.size();

    // 構建樹結構
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int p = par[i];
        g[p].push_back(i);
    }

    int ans = 0;

    // 使用pair表示mask和val
    using Pair = pair<int, int>;

    function<tuple<unordered_map<int, int>, vector<Pair>>(int)> dfs;
    dfs = [&](int x) -> tuple<unordered_map<int, int>, vector<Pair>> {
        unordered_map<int, int> f;
        vector<Pair> single;

        // 計算val的數位集合mask
        int val = vals[x];
        int mask = 0;
        int v = val;
        bool valid_mask = true;

        while (v > 0) {
            int d = v % D;
            if (mask >> d & 1) {
                valid_mask = false;
                break;
            }
            mask |= 1 << d;
            v /= D;
        }

        if (valid_mask && mask > 0) {
            f[mask] = val;
            single.emplace_back(mask, val);
        }

        for (int y : g[x]) {
            auto [fy, singleY] = dfs(y);

            // 啓發式合併：確保single是較大的那個
            if (singleY.size() > single.size()) {
                swap(single, singleY);
                swap(f, fy);
            }

            single.insert(single.end(), singleY.begin(), singleY.end());

            // 把子樹y中的mask和val一個一個地加到f中
            for (auto [msk, v_val] : singleY) {
                if (v_val <= f[msk]) {
                    continue;
                }

                unordered_map<int, int> nf = f;
                nf[msk] = v_val;

                for (auto [msk2, s2] : f) {
                    if ((msk & msk2) == 0) {
                        int combined_mask = msk | msk2;
                        nf[combined_mask] = max(nf[combined_mask], v_val + s2);
                    }
                }

                f = move(nf);
            }
        }

        // 更新答案
        int mx = 0;
        for (auto [_, s] : f) {
            mx = max(mx, s);
        }
        ans = (ans + mx) % mod;

        return {f, single};
    };

    dfs(0);
    return ans;
}

int main() {
    vector<int> vals = {3, 22, 5};
    vector<int> par = {-1, 0, 1};
    int result = goodSubtreeSum(vals, par);
    cout << result << endl;
    return 0;
}