首页 > 试题广场 >

神秘的苹果树

[编程题]神秘的苹果树

热度指数：4133 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团找到一颗有n个节点的苹果树，以1号节点为根，且每个节点都有一个苹果，苹果都有一个颜色，但是这棵树被施加了咒术，这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果，请帮帮她。每次她会指定一个节点t，如果小团只能从节点t的子树中选取某一种颜色的苹果，选取什么颜色能拿到最多的苹果？如果有多种颜色都可以拿同样多的苹果，输出颜色编号最小的那个对应的编号。

节点x的子树定义为所有将x当作祖先的节点，x也视为x的子树的一部分。

输入描述:

第一行一个正整数n表示这颗树上节点的个数。

接下来n-1行，每行两个正整数x_i,y_i,表示树上第i条边连接的两个节点。

接下来一行n个正整数c_i，分别表示从1~n号节点上的苹果的颜色。

接下来一行一个正整数q,表示接下来有q次独立的询问。

接下来q行，每行一个正整数t表示询问：如果小团只能从节点t的子树中选取某一种颜色的苹果，选取什么颜色能拿到最多的苹果？如果有多种颜色都可以拿同样多的苹果，输出颜色编号最小的那个对应的编号。

对于100%的数据n≤5000, 1≤x_i,y_i,t≤n, c_i≤1000000000,q≤1000

输出描述:

输出q行，每行一个整数，表示答案。

示例1

输入

7
1 2
1 3
2 4
2 5
3 6
3 7
1 1 2 1 2 2 3
7
1
2
3
4
5
6
7

输出

算法知识视频讲解

Python

努力，奋斗~

from collections import defaultdict
from functools import lru_cache

# 无根图转有根图
def modify(x, fa):
    flag = 0
    for y in tree[x]:
        if y == fa:
            flag = 1
            continue
        modify(y, x)
    if flag:
        tree[x].remove(fa)
# 记忆化搜索，或是设一个vis保存
@lru_cache
def dfs(r):
    # if r in vis:
    #     return vis[r]
    cnt = defaultdict(int)
    cnt[col[r - 1]] += 1
    for v in tree[r]:
        cnt_v = dfs(v)
        for k, v in cnt_v.items():
            cnt[k] += v
    # vis[r] = cnt
    return cnt

tree = defaultdict(list)
n = int(input())
for _ in range(n - 1):
    a, b = list(map(int, input().strip().split()))
    tree[a].append(b)
    tree[b].append(a)
modify(1, -1)
col = tuple(map(int, input().split()))
# vis = dict()
q = int(input())
for idx in range(q):
    t = int(input())
    cnt = dfs(t)
    cnt_l = list(cnt.items())
    cnt_l.sort(key=lambda x: [-x[1], x[0]])
    print(cnt_l[0][0])

发表于 2023-03-11 16:53:11 回复(0)