首页 > 试题广场 >

神秘的苹果树

[编程题]神秘的苹果树
  • 热度指数：4188 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

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

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


输入描述:
第一行一个正整数n表示这颗树上节点的个数。
接下来n-1行，每行两个正整数x­­i,yi,表示树上第i条边连接的两个节点。
接下来一行n个正整数c­i，分别表示从1~n号节点上的苹果的颜色。
接下来一行一个正整数q,表示接下来有q次独立的询问。
接下来q行，每行一个正整数t表示询问：如果小团只能从节点t的子树中选取某一种颜色的苹果，选取什么颜色能拿到最多的苹果？如果有多种颜色都可以拿同样多的苹果，输出颜色编号最小的那个对应的编号。
      
对于100%的数据n≤5000, 1≤xi,yi,t≤n, ci≤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

输出

1
1
2
1
2
2
3
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
35条回答 10068浏览

热门推荐

通过挑战的用户

相关试题

神秘的苹果树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号