神秘的苹果树

def getColor(name):
    #返回一个字典，包括以name的子树中每种颜色苹果的个数
    if name in treeColor:
        return treeColor[name]
    currentColor = {color[name-1]:1} #先把自己的颜色记录下来
    if name in tree:
        son = tree[name]
        for everySon in son:
            sonColor = getColor(everySon) #获得每个子节点的子树中的颜色计数
            for key in sonColor:
                if key in currentColor:
                    currentColor[key]+=sonColor[key]
                else:
                    currentColor[key]=sonColor[key]
    treeColor[name] = currentColor #将这个字典储存在treeColor[name]中，避免重复求值
    return currentColor

def findTree(name):
    #寻找以name为父节点的树
    if len(tree[name])>0:
        for son in tree[name]:
            tree[son].remove(name) #将son的父节点从tree[son]中删去，此时只有它的子节点
            findTree(son)

n = int(input())
connect = {}
tree = {}
for i in range(n-1):
    x, y = map(int,input().split())
    #tree[i]暂时存放和节点i相连的所有节点，包括父节点和子节点
    if x not in tree:
        tree[x]=[]
    tree[x].append(y)
    if y not in tree:
        tree[y]=[]
    tree[y].append(x)
color =tuple(map(int, input().split())) #储存每个节点的颜色

findTree(1)#找到以1为根节点的树后，tree[i]中储存i的子节点
treeColor={}
q=int(input())
for j in range(q):
    name = int(input())
    currentColor = getColor(name)
    num = 0
    for key in currentColor.keys():
        #寻找个数最多的颜色
        if currentColor[key]>num:
            num = currentColor[key]
            maxColor = key
        elif currentColor[key]==num:
            if key<maxColor:
                maxColor = key
    print(maxColor)
    

#include <iostream>
#include <vector>
#include <map>
using namespace std;

map<int, int> process(vector<vector<int>>& edges, vector<int>& color, vector<int>& dp, int fa, int curr){
    map<int, int> mp;
    mp[color[curr]]++;

    for(auto c : edges[curr]){
        if(c == fa)
            continue;
        map<int, int> temp = process(edges, color, dp, curr, c);
        for(auto it : temp){
            mp[it.first] += it.second;
        }
    }

    int maxVal = 0, colorId = -1;
    for(auto it : mp){
        if(maxVal < it.second){
            maxVal = max(maxVal, it.second);
            colorId = it.first;
        }
    }
    dp[curr] = colorId;
    return mp;
}


int main(){
    int n;
    cin >> n;
    vector<vector<int>> edges(n+1);
    for(int i = 0; i < n-1; i++){
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    vector<int> color(n+1);
    
    for(int i = 1; i <= n; i++){
        cin >> color[i];
    }

    vector<int> dp(n+1, 0);
    process(edges, color, dp, 0, 1);
    int q;
    cin >> q;
    while(q--){
        int t;
        cin >> t;
        cout << dp[t] << endl;
    }
    return 0;
}

C++, 将有向图转化为无向图，然后dfs遍历

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, e1, e2;
    cin >> n;
    unordered_set<int> g[n + 1];
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d %d", &e1, &e2);
        g[e1].insert(e2);
        g[e2].insert(e1);
    }

    int color[n + 1];   // 存储每个节点对应的颜色
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &color[i]);
    }


    // 将无向图转化为有向图, 即删除子节点指向父节点的边
    function<void(int, int)> dfs = [&](int u, int p) -> void {
        g[u].erase(p);
        for (int v : g[u]) {
            dfs(v, u);
        }
    };
    dfs(1, -1);

    map<int, int> cnts;  // 记录当前遍历子树的颜色及颜色对应的次数
    function<void(int)> dfs2 = [&](int u) {
        cnts[color[u]]++;
        for (int v : g[u]) {
            dfs2(v);
        }
    };

    int q; cin >> q;
    while (q--) {   // dfs枚举答案
        cnts.clear();
        int node; cin >> node;
        dfs2(node);
        int ma = 0, resColor = -1;
        for (auto [colorIdx, cnt] : cnts) { 
            if (cnt > ma) {
                ma = cnt;
                resColor = colorIdx;
            }
        }
        cout << resColor << endl;
    }
    return 0;
}

/*
题目只知道1为根节点，输入边时不知道哪个是父节点，需要先构建无向树。然后
从根节点1开始向下递归删除子节点指向父节点，改为有向树
*/ 
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] arr=new Node[n+1];
        for(int i=0;i<n+1;++i){  //初始化
            arr[i]=new Node();
        }
        for(int i=0;i<n-1;i++){
            int a= scanner.nextInt(); 
            int b= scanner.nextInt();
            arr[a].sonList.add(arr[b]);
            arr[b].sonList.add(arr[a]);
        }
        adjust(arr[1],arr);
        for(int i=1;i<n+1;++i){
            int c = scanner.nextInt();
            arr[i].c=c;
        }
        Map<Integer,Integer> cnt = new TreeMap<>();//每个颜色对应的个数,用Treemap排序后面找最小的
        int time = scanner.nextInt();
        for(int i=0;i<time;i++){
            int root = scanner.nextInt();
            Dfs(arr[root],arr,cnt);
            List<Integer> list =new ArrayList<>(cnt.values()); //map的value转为list
            Collections.sort(list);
            for(Map.Entry entry: cnt.entrySet()){
                if(entry.getValue() == list.get(list.size()-1)){
                    System.out.println(entry.getKey());
                    break;
                }
            }
            cnt.clear();  //清空map
        }
    }
    public static void Dfs(Node node,Node[] arr,Map<Integer,Integer> cnt){
        int c = node.c;
        cnt.put(c,cnt.getOrDefault(c,0)+1); //map中有c就返回对应value，否则返回0
       // if(node.sonList.size()==0)return;  //不用出口也行，不用回溯
        for(Node n:node.sonList){
            Dfs(n,arr,cnt);
        }
    }
    public static void  adjust(Node node,Node[] arr){  //无向图变有向图
            List<Node> sonList = node.sonList;
            //if(sonList.size()==0) return;
            for(Node n:sonList){
                List<Node> ssonList = n.sonList;
                ssonList.remove(node);
                n.sonList=ssonList;
                adjust(n,arr);
            }
    }
    static class Node{
        int c;  //颜色
        List<Node> sonList=new ArrayList<>();  //子节点
     }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
 
public class Main
{
     
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        HashMap<Integer,TreeNode> map = new HashMap<>();
        int connect = sc.nextInt();
        for (int i = 0; i < connect-1; i++)
        {
            int parentNode = sc.nextInt();
            int sonNode = sc.nextInt();
            TreeNode pNode = map.getOrDefault(parentNode-1, new TreeNode(parentNode));
            TreeNode sNode = map.getOrDefault(sonNode-1,new TreeNode(sonNode));
            if (pNode.left!=null)pNode.right = sNode;
            else pNode.left = sNode;
            map.put(parentNode-1,pNode);
            map.put(sonNode-1,sNode);
        }
        //然后开始给每个染色
        List<Integer> colorList = new ArrayList<>();
        for (int i = 0; i < connect; i++)
        {
            colorList.add(sc.nextInt());
        }
        for (int i = connect-1; i >=0; --i)
        {
            TreeNode treeNode = map.get(i);
            treeNode.color = colorList.get(i);
            treeNode.colorNum = new int[connect];
            int[] colorNum = treeNode.colorNum;
            colorNum[treeNode.color-1]++;
            if (treeNode.left==null&&treeNode.right==null)
            {
                treeNode.maxColor = treeNode.color;
            }
            else if (treeNode.right==null)
            {
                int[] leftColorNum = treeNode.left.colorNum;
                int maxColor = -1;
                int maxCount = 0;
                for (int j = 0; j < colorNum.length; j++)
                {
                    colorNum[j]+=leftColorNum[j];
                    if (colorNum[j]>maxCount)
                    {
                        maxColor = j;
                    }
                }
                treeNode.maxColor = maxColor+1;
            }
            else
            {
                int[] leftColorNum = treeNode.left.colorNum;
                int[] rightColorNum = treeNode.right.colorNum;
                int maxColor = -1;
                int maxCount = 0;
                for (int j = 0; j < colorNum.length; j++)
                {
                    colorNum[j]+=(leftColorNum[j]+rightColorNum[j]);
                    if (colorNum[j]>maxCount)
                    {
                        maxColor = j;
                        maxCount = colorNum[j];
                    }
                }
                treeNode.maxColor = maxColor+1;
            }
        }
        //
        int time = sc.nextInt();
        for (int i = 0; i < time; i++)
        {
            System.out.println(map.get(sc.nextInt()-1).maxColor);
        }
         
    }
    static class TreeNode
    {
        int color;
        int num;
        int maxColor;
        int[] colorNum;
        TreeNode left;
        TreeNode right;
        TreeNode(int num)
        {
            this.num = num;
        }
    }
}

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])

import java.util.*;

public class Main {
    public static HashMap<Integer, Integer> map;
    public static void dfs(List<Integer>[] graph, int[] col_arr, int root) {
        map.put(col_arr[root], map.getOrDefault(col_arr[root], 0)+1);
        for(int neigh:graph[root]) {
            dfs(graph, col_arr, neigh);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int numOfNode=Integer.parseInt(sc.nextLine());
        int numOfEdges=numOfNode-1;
        LinkedList<Integer>[] graph=new LinkedList[numOfNode+1];
        for(int i=1; i<=numOfNode; i++) graph[i]=new LinkedList<>();
        
        while(numOfEdges>0) {
            String[] edge_info=sc.nextLine().split(" ");
            int from=Integer.parseInt(edge_info[0]), to=Integer.parseInt(edge_info[1]);
            graph[from].add(to);
            graph[to].add(from);
            numOfEdges--;
        }
        
        String[] col_info=sc.nextLine().split(" ");
        int[] col_arr=new int[col_info.length+1];
        for(int i=1; i<=col_info.length; i++) col_arr[i]=Integer.parseInt(col_info[i-1]);
        
        Queue<Integer> queue=new LinkedList<>();
        queue.add(1);
        while(!queue.isEmpty()) {
            int node=queue.poll();
            List<Integer> tmp=graph[node];
            for(int neigh:tmp) {
                queue.add(neigh);
                int idx=0;
                for(; idx<graph[neigh].size(); idx++) {
                    if(graph[neigh].get(idx)==node) break;
                }
                graph[neigh].remove(idx);
            }
        }

        int n=Integer.parseInt(sc.nextLine());
        
        while(n>0) {
            int root=Integer.parseInt(sc.nextLine());
            map=new HashMap<>();
            dfs(graph, col_arr, root);
            int max_num=0;
            int res=-1;
            for(int col:map.keySet()) {
                if(map.get(col)>max_num) {
                    max_num=map.get(col);
                    res=col;
                } else if(map.get(col)==max_num) {
                    res=Math.min(col, res);
                }
            }
            n--;
            System.out.println(res);
        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
//原始关系树
        List<Integer>[] list = new ArrayList[n+1];
//最终有向树
        List<Integer>[] tree = new ArrayList[n+1];
//先初始化有向树
        for (int i = 1; i < n + 1; i++) {
            ArrayList<Integer> list1 = new ArrayList<>();
            tree[i]=list1;
        }
//构建原始关系树
        for(int i=0;i<n-1;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            if(list[x]==null){
                ArrayList<Integer> nodes=new ArrayList<>();
                nodes.add(y);
                list[x]=nodes;
            }else{
                list[x].add(y);
            }
            if(list[y]==null){
                ArrayList<Integer> nodes=new ArrayList<>();
                nodes.add(x);
                list[y]=nodes;
            }else{
                list[y].add(x);
            }
        }
//记录树节点的颜色
        int[] colour =new int[n+1];
        boolean[] visted=new boolean[n+1];
        for(int i=1;i<n+1;i++){
            colour[i]=sc.nextInt();
        }
//开始bfs对最终树的构建
        int q=sc.nextInt();
        Queue<Integer> queue=new ArrayDeque<>();
        queue.offer(1);
        while(!queue.isEmpty()){
            int parent=queue.poll();
            visted[parent]=true;
            for(Integer child:list[parent]){
                if(!visted[child]){
                    queue.offer(child);
                    tree[parent].add(child);
                }
            }
        }
//开始处理请求
        for(int i=0;i<q;i++){
//获得节点，记录节点的颜色和数量为1
            int node =sc.nextInt();
            HashMap<Integer, Integer> colour_number = new HashMap<>();
            colour_number.put(colour[node],1);
//开始bfs遍历节点的颜色数量
            queue.offer(node);
            while(!queue.isEmpty()){
                int root=queue.poll();
                for(Integer son:tree[root]){
//如果没有该颜色，说明是第一次遇到，记录它的值为1
                    if(!colour_number.containsKey(colour[son])){
                        colour_number.put(colour[son],1);
                        queue.offer(son);
                    }else {
//遇到过了，就把它的数量加1
                        Integer integer = colour_number.get(colour[son])+1;
                        colour_number.put(colour[son],integer);
                        queue.offer(son);
                    }
                }
            }
            int max=0;
            int c_min=0;
//最后遍历map集合，获得符合题目的颜色
           for (Integer integer : colour_number.keySet()) {
                if(colour_number.get(integer)>max){
                    c_min=integer;
                    max=colour_number.get(integer);
                }else if (colour_number.get(integer)==max){
                    c_min=Math.min(c_min,integer);
                }
            }
            System.out.println(c_min);
        }
    }
}

import java.io.*;
import java.util.*;
public class Main{
    public static class Node{
        int node;
        int max_color;
        HashMap<Integer,Integer> map;//存以node为根节点的所有子节点上的各个color数量
        public Node(int n){
            this.node = n;
            this.max_color = -1;
            this.map = new HashMap<>();
        }
    }
    public static void postOrder(HashMap<Integer,ArrayList<Integer>> graph, Node[] array_node, int[] nodeTocolor, int parent, int no){

        int max_color = -1,max = -1;
        HashMap<Integer,Integer> current_map = array_node[no].map;
        ArrayList<Integer> list = graph.get(no);
        if(list.size() == 1 && list.get(0).equals(parent)){
            current_map.put(nodeTocolor[no],1);
            array_node[no].max_color = nodeTocolor[no];
            return;
        }
        for(int next : list){
            if(next == parent) continue;
            postOrder(graph,array_node,nodeTocolor,no,next);
            HashMap<Integer,Integer> next_map = array_node[next].map;
            for(int key_color : next_map.keySet()){
                current_map.put(key_color,current_map.getOrDefault(key_color,0) + next_map.get(key_color));
            }
        }
        current_map.put(nodeTocolor[no],current_map.getOrDefault(nodeTocolor[no],0)+1);
        for(int key_color : current_map.keySet()){
            int value = current_map.get(key_color);
            if(value > max){
                max = value;
                max_color = key_color;
            }
            else if(value == max) max_color = Math.min(max_color,key_color);
        }
        array_node[no].max_color = max_color;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = " ";
        while((str = br.readLine()) != null){
            int n = Integer.parseInt(str);
            Node[] array_node = new Node[n+1];
            for(int i = 1; i <= n; ++i) array_node[i] = new Node(i);
            HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();
            String[] str_array;
            for(int l = 0; l < n-1; ++l){
                str_array = br.readLine().split(" ");
                int n1 = Integer.parseInt(str_array[0]);
                int n2 = Integer.parseInt(str_array[1]);
                if(graph.getOrDefault(n1,null) == null) graph.put(n1,new ArrayList<>());
                if(graph.getOrDefault(n2,null) == null) graph.put(n2,new ArrayList<>());
                graph.get(n1).add(n2);
                graph.get(n2).add(n1);
            }
            int[] nodeTocolor = new int[n+1];
            str_array = br.readLine().split(" ");
            for(int i = 1; i <= n; i++) nodeTocolor[i] = Integer.parseInt(str_array[i-1]);
            postOrder(graph,array_node,nodeTocolor,0,1);
            int q = Integer.parseInt(br.readLine());
            StringBuilder builder = new StringBuilder();
            for(int i = 0; i < q; ++i){
                int q_n = Integer.parseInt(br.readLine());
                builder.append(array_node[q_n].max_color).append('\n');
            }
            System.out.print(builder);
        }
    }
}

/*
* modify 借鉴评论 其他暴力解决
*/
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Main {

    static HashMap<Integer, List<Integer>> graph;
    static HashMap<Integer, Integer> mp;
    static int maxn;
    static int maxcolor;
    static int colos[];
    static void modify(int root){
        if(graph.containsKey(root)){
            List<Integer> th = graph.get(root);
            for (int i = 0; i < th.size(); i++) {
                List<Integer> th1 = graph.get(th.get(i));
                int delete = -1;
                for(int j = 0; j < th1.size(); j++){
                    if(th1.get(j) == root){
                        delete = j;
                        break;
                    }
                }
                graph.get(th.get(i)).remove(delete);
                modify(th.get(i));
            }
        }
    }
    static void dfs(int node){
        if(!graph.containsKey(node)){
            return;
        }
        List<Integer> th = graph.get(node);
        for(int i = 0; i < th.size(); i++){
            int tc = colos[th.get(i)-1];
            int tn = mp.getOrDefault(tc, 0) + 1;
            mp.put(tc, tn);
            if(tn > maxn || tn == maxn && maxcolor > tc){
                maxn = tn;
                maxcolor = tc;
            }
            dfs(th.get(i));
        }
    }
    //构建树或者图 然后暴力遍历
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        graph = new HashMap<>();
        mp = new HashMap<>();
        String[] strs;

        colos = new int[n];
        for(int i = 0; i < n - 1; i++){
            strs = br.readLine().split(" ");
            int a = Integer.parseInt(strs[0]);
            int b = Integer.parseInt(strs[1]);
            if(!graph.containsKey(a)){
                graph.put(a, new ArrayList<>());
            }
            if(!graph.containsKey(b)){
                graph.put(b, new ArrayList<>());
            }
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        modify(1);
        strs = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            colos[i] = Integer.parseInt(strs[i]);
        }
        int m = Integer.parseInt(br.readLine());
        int ret[] = new int[m];
        for (int i = 0; i < m; i++) {

            int node = Integer.parseInt(br.readLine());
            mp.clear();
            mp.put(colos[node-1], 1);
            maxn = 1;
            maxcolor = colos[node-1];
            dfs(node);
            ret[i] = maxcolor;
        }
        for(int i = 0; i < m; i++){
            bw.write(Integer.toString(ret[i]));
            bw.newLine();
            bw.flush();
        }
    }
}