小团找到一颗有n个节点的苹果树,以1号节点为根,且每个节点都有一个苹果,苹果都有一个颜色,但是这棵树被施加了咒术,这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果,请帮帮她。每次她会指定一个节点t,如果小团只能从节点t的子树中选取某一种颜色的苹果,选取什么颜色能拿到最多的苹果?如果有多种颜色都可以拿同样多的苹果,输出颜色编号最小的那个对应的编号。
节点x的子树定义为所有将x当作祖先的节点,x也视为x的子树的一部分。
小团找到一颗有n个节点的苹果树,以1号节点为根,且每个节点都有一个苹果,苹果都有一个颜色,但是这棵树被施加了咒术,这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果,请帮帮她。每次她会指定一个节点t,如果小团只能从节点t的子树中选取某一种颜色的苹果,选取什么颜色能拿到最多的苹果?如果有多种颜色都可以拿同样多的苹果,输出颜色编号最小的那个对应的编号。
节点x的子树定义为所有将x当作祖先的节点,x也视为x的子树的一部分。
第一行一个正整数n表示这颗树上节点的个数。
接下来n-1行,每行两个正整数xi,yi,表示树上第i条边连接的两个节点。
接下来一行n个正整数ci,分别表示从1~n号节点上的苹果的颜色。
接下来一行一个正整数q,表示接下来有q次独立的询问。
接下来q行,每行一个正整数t表示询问:如果小团只能从节点t的子树中选取某一种颜色的苹果,选取什么颜色能拿到最多的苹果?如果有多种颜色都可以拿同样多的苹果,输出颜色编号最小的那个对应的编号。
对于100%的数据n≤5000, 1≤xi,yi,t≤n, ci≤1000000000,q≤1000
输出q行,每行一个整数,表示答案。
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
public class Main { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int TreeSize = scanner.nextInt(); Map<Integer,List<Integer>> map = new HashMap<>(); for(int i=0;i<TreeSize-1;i++){ int father = scanner.nextInt(); int son = scanner.nextInt(); List<Integer> fatherList = map.getOrDefault(father,new ArrayList<Integer>()); List<Integer> sonList =map.getOrDefault(son,new ArrayList<Integer>()); fatherList.add(son); sonList.add(father); map.put(father,fatherList); map.put(son,sonList); } modify(1,map); //root是1 这是已知条件 //对map里面的元素进行modyfy 使得它只能含有指向儿子的有向图 //开始通过map 进行dfs遍历 并统计 数量 //1.查字典 id 对应的 颜色 Map<Integer,Integer> dictionary = new HashMap<>(); Map<Integer,Integer> counter = new TreeMap<>();//计数器 for(int i=0;i<TreeSize;i++){ int color = scanner.nextInt(); dictionary.put(i+1,color); } int time = scanner.nextInt(); for(int i=0;i<time;i++){ int root = scanner.nextInt(); Dfs(root,dictionary,counter,map); List<Integer> list =new ArrayList<>(counter.values()); Collections.sort(list); //现在想知道 list.szie-1 这个数量的key for(Map.Entry entry: counter.entrySet()){ if(entry.getValue() == list.get(list.size()-1)){ System.out.println(entry.getKey()); break; } } //清空counter counter.clear(); } } public static void Dfs(int root,Map<Integer,Integer> dictionary,Map<Integer,Integer> counter,Map<Integer,List<Integer>> map){ //1.把root的color加入 int color = dictionary.get(root); counter.put(color,counter.getOrDefault(color,0)+1); for(int child: map.get(root)){ Dfs(child,dictionary,counter,map); } } public static void modify(Integer root, Map<Integer,List<Integer>> map){ List<Integer> fatherList = map.get(root); if(fatherList.size()==0){ return;//递归的终点 } for(Integer child:fatherList){ List<Integer> children = map.get(child); children.remove(root); //删除child为键的 邻接数组里面是root的部分 map.put(child,children); modify(child,map); } } }
from queue import Queue from collections import defaultdict def bfs(root, tree): queue = Queue() queue.put(root) children = [root] while not queue.empty(): cur = queue.get() if cur in tree: # 还没到叶子节点 for child in tree[cur]: queue.put(child) children.append(child) return children def modify(root): if tree[root]: for child in tree[root]: # 将子节点指向父节点的关系删除 tree[child].remove(root) modify(child) if __name__ == "__main__": n = int(input()) tree = defaultdict(lambda: []) for _ in range(n - 1): x, y = map(int, input().strip().split()) tree[x].append(y) tree[y].append(x) # 根据拓扑关系,将树改为有向图 modify(1) colors = tuple(map(int, input().strip().split())) q = int(input()) for _ in range(q): t = int(input()) # bfs获得节点t的所有子节点(包括自己) children = bfs(t, tree) # 颜色计数器 counter = defaultdict(lambda: 0) for child in children: counter[colors[child - 1]] += 1 # 输出数量最多的颜色 maxColor = 5001 maxCount = 0 for color in counter: if maxCount < counter[color]: maxCount = counter[color] maxColor = color elif maxCount == counter[color]: maxColor = min(color, maxColor) print(maxColor)
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; }
import java.util.*; class TreeNode{ int val; int color; List<TreeNode> Friend =new ArrayList<>(); public TreeNode(int val){ this.val=val; } } public class Main{ public static void modify(TreeNode root){ if(root.Friend.size()==0){ return; } for (TreeNode node : root.Friend) { node.Friend.remove(root); modify(node); } } public static void dfs(TreeNode root,Map<Integer,Integer> colormap){ if(root==null)return; colormap.put(root.color, colormap.getOrDefault(root.color,0)+1); for (TreeNode treeNode : root.Friend) { dfs(treeNode,colormap); } } public static void main(String[] args){ /*第一行一个正整数n表示这颗树上节点的个数。 接下来n-1行,每行两个正整数xi,yi,表示树上第i条边连接的两个节点。 接下来一行n个正整数ci,分别表示从1~n号节点上的苹果的颜色。 接下来一行一个正整数q,表示接下来有q次独立的询问。 接下来q行,每行一个正整数t表示询问:如果小团只能从节点t的子树中选取某一种颜色的苹果,选取什么颜色能拿到最多的苹果? 如果有多种颜色都可以拿同样多的苹果,输出颜色编号最小的那个对应的编号。 节点x的子树定义为所有将x当作祖先的节点,x也视为x的子树的一部分。 */ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); Map<Integer, TreeNode> map=new HashMap<>(); for(int i=0;i<n-1;i++){ int x=sc.nextInt(); int y=sc.nextInt(); TreeNode node1=map.get(x); TreeNode node2=map.get(y); if(node1==null)node1=new TreeNode(x); if(node2==null)node2=new TreeNode(y); node1.Friend.add(node2); node2.Friend.add(node1); map.put(x,node1); map.put(y,node2); } modify(map.get(1)); for(int i=1;i<=n;i++){ int color=sc.nextInt(); map.get(i).color=color; } int q=sc.nextInt(); for(int i=0;i<q;i++){ Map<Integer,Integer> colormap=new HashMap<>(); int t=sc.nextInt(); TreeNode root=map.get(t); dfs(root,colormap); int bestColor=0; int count=0; for (Map.Entry<Integer, Integer> entry : colormap.entrySet()) { if(entry.getValue()==count)bestColor=Math.min(entry.getKey(),bestColor); else if(entry.getValue()>count){ bestColor=entry.getKey(); count=entry.getValue(); } } System.out.println(bestColor); } } }
#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<>(); //子节点 } }
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define rep(i,a,b) for(int i = (a);i <= (b);++i) #define re_(i,a,b) for(int i = (a);i < (b);++i) #define dwn(i,a,b) for(int i = (a);i >= (b);--i) const int N = 5e3 + 5; int n,m,a[N]; vector<int> G[N];int dfn[N][2],dfs_clk = 0; int lim,val[N]; int num[N],cnta = 0,cntc = 0,ans[N];set<int> big[N]; int bl[N],bsz; struct Qry{ int idx,l,r; Qry(){} Qry(int i,int l,int r):idx(i),l(l),r(r){} bool operator < (const Qry &rh) const{ return bl[l] ^ bl[rh.l] ? bl[l] < bl[rh.l] : r < rh.r; } }q[N]; void dbg(){puts("");} template<typename T, typename... R>void dbg(const T &f, const R &... r) { cout << f << " "; dbg(r...); } template<typename Type>inline void read(Type &xx){ Type f = 1;char ch;xx = 0; for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0'; xx *= f; } void dfs(int u,int ufa){ dfn[u][0] = ++dfs_clk; for(int &v: G[u]){ if(v == ufa) continue; dfs(v,u); } dfn[u][1] = dfs_clk; } void init(){ rep(i,1,n) val[i] = a[i]; sort(val+1,val+n+1); lim = unique(val+1,val+n+1)-val-1; rep(i,1,n) a[i] = lower_bound(val+1,val+lim+1,a[i]) - val; bsz = sqrt(n); rep(i,1,n) bl[i] = i / bsz + 1; dfs(1,0); vector<int> aa(n+1); rep(u,1,n) aa[dfn[u][0]] = a[u]; rep(i,1,n) a[i] = aa[i]; } inline void ad(int idx){ int v = num[a[idx]]; ++num[a[idx]]; big[v].erase(a[idx]); big[v+1].insert(a[idx]); if(v+1 == cnta) cntc = *big[cnta].begin(); if(v == cnta) ++cnta,cntc = *big[cnta].begin(); } inline void dc(int idx){ int v = num[a[idx]]; --num[a[idx]]; big[v].erase(a[idx]); big[v-1].insert(a[idx]); if(v == cnta){ if(!big[cnta].size()) --cnta; cntc = *big[cnta].begin(); } } void solve(){ int L = 1,R = 0; rep(i,1,m){ int ql = q[i].l,qr = q[i].r; while(R < qr) ad(++R); while(L > ql) ad(--L); while(R > qr) dc(R--); while(L < ql) dc(L++); ans[q[i].idx] = val[cntc]; } } int main(int argc, char** argv) { read(n); re_(_,1,n){ int x,y;read(x);read(y); G[x].push_back(y); G[y].push_back(x); } rep(i,1,n) read(a[i]); init(); read(m); rep(i,1,m){ int x;read(x);q[i] = {i,dfn[x][0],dfn[x][1]}; } sort(q+1,q+m+1); solve(); rep(i,1,m) printf("%d\n",ans[i]); return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define rep(i,a,b) for(int i = (a);i <= (b);++i) #define re_(i,a,b) for(int i = (a);i < (b);++i) #define dwn(i,a,b) for(int i = (a);i >= (b);--i) const int SZ = 5e3 + 5; int n,m,a[SZ]; vector<int> G[SZ]; int lim,val[SZ]; int son[SZ],siz[SZ]; int num[SZ],cnta = 0,cntc = 0,ans[SZ]; template<typename Type>inline void read(Type &xx){ Type f = 1;char ch;xx = 0; for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0'; xx *= f; } void init(){ rep(i,1,n) val[i] = a[i]; sort(val+1,val+n+1); lim = unique(val+1,val+n+1)-val-1; rep(i,1,n) a[i] = lower_bound(val+1,val+lim+1,a[i]) - val; } void change(int u){ ++num[a[u]]; if(num[a[u]] == cnta) cntc = min(cntc,a[u]); if(num[a[u]] > cnta){ cnta++;cntc = a[u]; } } void add(int u,int ufa){ change(u); for(int v: G[u]) if(v != ufa) add(v,u); } void dec(int u,int ufa){ --num[a[u]];cnta = cntc = 0; for(int &v: G[u]) if(v != ufa) dec(v,u); } void dfs1(int u,int ufa){ siz[u] = 1;son[u] = 0;int mx = 0; for(int &v: G[u]){ if(v == ufa) continue; dfs1(v,u); siz[u] += siz[v]; if(siz[v] > mx) son[u] = v,mx = siz[v]; } } void dfs2(int u,int ufa){ for(int &v: G[u]){ if(v == ufa || v == son[u]) continue; dfs2(v,u); dec(v,u); } if(son[u]) dfs2(son[u],u); for(int &v: G[u]){ if(v == ufa || v == son[u]) continue; add(v,u); } change(u); ans[u] = val[cntc]; } int main(int argc, char** argv) { read(n); re_(_,1,n){ int x,y;read(x);read(y); G[x].push_back(y); G[y].push_back(x); } rep(i,1,n) read(a[i]); init(); dfs1(1,0); dfs2(1,0); read(m); rep(i,1,m){ int x;read(x); printf("%d\n",ans[x]); } return 0; }
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; } } }有大哥告诉我 我这为什么错吗 在idea上明明是对的
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); } } }bfs,数据处理让我头疼,把自己搞晕了
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); } } }
package main import ( "bufio" "fmt" "math" "os" "strconv" "strings" ) func main() { sc := bufio.NewScanner(os.Stdin) bs := make([]byte, 1024*64) sc.Buffer(bs, len(bs)) sc.Scan() n, _ := strconv.Atoi(sc.Text()) vi := make(map[int][]int) for i := 1; i < n; i++ { sc.Scan() line := strings.Fields(sc.Text()) a, _ := strconv.Atoi(line[0]) b, _ := strconv.Atoi(line[1]) vi[a] = append(vi[a], b) vi[b] = append(vi[b], a) } var Modify func(root int) Modify = func(root int) { rootList := vi[root] if len(rootList) == 0 { return } for _, child := range rootList { childList := vi[child] newChildList := []int{} for _, childchild := range childList { if childchild != root { newChildList = append(newChildList, childchild) } } vi[child] = newChildList Modify(child) } } Modify(1) sc.Scan() colorLine := strings.Fields(sc.Text()) colorList := make([]int, len(colorLine)) for i, c := range colorLine { colorList[i], _ = strconv.Atoi(c) } sc.Scan() queryTimes, _ := strconv.Atoi(sc.Text()) queryList := make([]int, queryTimes) for i := 0; i < queryTimes; i++ { sc.Scan() queryList[i], _ = strconv.Atoi(sc.Text()) } colorDict := make(map[int]int) for i, c := range colorList { colorDict[i+1] = c } colorCounter := make(map[int]int) var Dfs func(root int) Dfs = func(root int) { color := colorDict[root] colorCounter[color]++ for _, child := range vi[root] { Dfs(child) } } for _, q := range queryList { Dfs(q) colorCounterList := []int{} for _, v := range colorCounter { colorCounterList = append(colorCounterList, v) } maxCount := 0 for _, c := range colorCounterList { maxCount = max(maxCount, c) } keyList := []int{} for k, v := range colorCounter { if v == maxCount { keyList = append(keyList, k) } } minKey := math.MaxInt32 for _, k := range keyList { minKey = min(minKey, k) } fmt.Println(minKey) for k := range colorCounter { delete(colorCounter, k) } } } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
n=int(input()) dic={} for i in range(n-1): a,b=map(int,input().split()) dic.setdefault(a,[]).append(b) colors=list(map(int,input().split())) q=int(input()) for i in range(q): node=int(input()) if not node in dic: print(colors[node-1]) continue top=0 rear=1 temp=[] temp.append(node) col={} while top<rear: node=temp[top] color=colors[node-1] if not color in col: col[color]=1 else: col[color]+=1 if node in dic: for item in dic[node]: temp.append(item) rear=rear+1 top=top+1 #print(col) mcol=max(col,key=lambda x:col[x]) print(mcol)
import java.util.*; public class Main { public static void main(String[] args) { // 因为是不成环的图所以边数为节点数 - 1 Scanner sc = new Scanner(System.in); int nodeNum = sc.nextInt(); // 先使用ColorNode[]来存储所有结点并构建:无向无权不成环的图 ColorNode[] nodes = new ColorNode[nodeNum + 1]; for (int i = 0; i < nodeNum - 1; i++) { int u = sc.nextInt(); int v = sc.nextInt(); if (nodes[u] == null) { nodes[u] = new ColorNode(); } if (nodes[v] == null) { nodes[v] = new ColorNode(); } nodes[v].subTree.add(nodes[u]); nodes[u].subTree.add(nodes[v]); } // 无向图变为有向图 modify(nodes[1]); sc.nextLine(); // 设置颜色 String[] split = sc.nextLine().split(" "); for (int i = 1; i <= nodeNum; i++) { nodes[i].color = Integer.valueOf(split[i - 1]); } // 记录开始的结点编号 int loop = sc.nextInt(); int[] res = new int[loop]; int[] opNum = new int[loop]; sc.nextLine(); for (int i = 0; i < loop; i++) { opNum[i] = Integer.valueOf(sc.nextLine()); } // 遍历要操作的结点 for (int i = 0; i < loop; i++) { int opeNode = opNum[i]; // 深搜并将结果保存在map中 HashMap<Integer, Integer> map = new HashMap<>(); dfs(nodes[opeNode], map); // 按照value降序排序 List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet()); Collections.sort(list, (Map.Entry<Integer, Integer> entry1, Map.Entry<Integer, Integer> entry2) -> { return entry2.getValue() - entry1.getValue(); }); // 找到符合要求的颜色 int curRes = list.get(0).getKey(); int curMaxNum = list.get(0).getValue(); int j = 1; // 如果出现重复的最大数量颜色编号,则找到最小的那个 while (j < list.size() && list.get(j).getValue() == curMaxNum) { curRes = list.get(j).getKey() < curRes ? list.get(j).getKey() : curRes; j++; } // 保存结点 res[i] = curRes; } // 打印结果 for (int i = 0; i < res.length; i++) { System.out.println(res[i]); } } // 深搜:类似前序遍历 public static void dfs(ColorNode root, HashMap<Integer, Integer> map) { if (root == null) return; int color = root.color; Integer aDefault = map.getOrDefault(color, -1); if (aDefault == -1) { // 说明当前颜色第一次被检测到 map.put(color, 1); } else { map.put(color, aDefault + 1); } for (ColorNode subNode : root.subTree) { dfs(subNode, map); } } // 从无向树变为有向树(层序遍历) public static void modify(ColorNode root) { ArrayDeque<ColorNode> deque = new ArrayDeque<>(); deque.addLast(root); while (deque.size() != 0) { int size = deque.size(); for (int i = 0; i < size; i++) { ColorNode first = deque.removeFirst(); for (ColorNode curSub : first.subTree) { deque.addLast(curSub); curSub.subTree.remove(first); } } } } static class ColorNode { int color; ArrayList<ColorNode> subTree; public ColorNode() { this.color = -1; this.subTree = new ArrayList<>(); } } }
/* * 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(); } } }