很久很久以前,在蚂蚁森林里住着 只小动物,编号从 到 。编号越小的动物能力值越大。现在他们想投票选出一只小动物当森林之王,对于每只小动物来说,如果他有崇拜的对象,那么他可能投票选择自己,或与自己崇拜的对象投相同票;如果他没有崇拜的对象,那么他投票只可能选择自己。
每只小动物只会崇拜能力值比自己大的小动物。
记者小强拜访了这 只小动物,了解到每只小动物是否有崇拜的对象以及具体是谁。现在他想知道每个人能得到的最高票数是多少。
第一行一个正整数 ,代表小动物的数量。
第二行 个以空格分隔的正整数 ,代表每只小动物崇拜的小动物。
若 ,则代表第 只小动物没有崇拜的对象。
。
保证 。
共 行,第 行代表第 只小动物可能得到的最多票数。
4 0 1 1 1
4 1 1 1
如果第 只小动物均和第一只投一样的票,则第一只小动物可以获得四票。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] strParams = br.readLine().trim().split(" "); int[] worshipId = new int[n + 1]; int[] tickets = new int[n + 1]; Arrays.fill(tickets, 1); for(int i = 0; i < n; i++) worshipId[i + 1] = Integer.parseInt(strParams[i]); for(int i = n; i >= 1; i--) tickets[worshipId[i]] += tickets[i]; // 有崇拜对象,假设把自己身上所有的票都投给崇拜对象 for(int i = 1; i <= n; i++) System.out.println(tickets[i]); } }scala版
import scala.io.StdIn object Main { def main(args: Array[String]): Unit = { val n = StdIn.readInt val strArr = StdIn.readLine.split(" ") val worshipId = Array.ofDim[Int](n + 1) val tickets = Array.ofDim[Int](n + 1) for(i <- 0 to n - 1) worshipId(i + 1) = strArr(i).toInt; for(i <- n to 1 by -1){ tickets(i) += 1 // 自己有一票 tickets(worshipId(i)) += tickets(i) // 把所有的票给自己的偶像 } for(i <- 1 to n) println(tickets(i)) } }
把每个小动物看作有向图的一个节点, 只能够由低能力的指向高能力的, 那么从能力值最低的开始遍历将可以遍历到所有小动物, 只需要再遍历的过程中记录相应次数即可
#include <iostream> #include <vector> using namespace std; #define int long long void dfs(int u, vector<vector<int> > &edg, vector<int> & siz) { siz[u] = 1; for(const int &t : edg[u]) { dfs(t, edg, siz); siz[u] += siz[t]; } } signed main() { int n; cin >> n; vector<int> fa(n); vector<vector<int> > edg(n); for(int i = 0; i < n; ++ i) { cin >> fa[i]; -- fa[i]; if(fa[i] != -1) edg[fa[i]].push_back(i); } vector<int> siz(n, 0); for(int i = 0; i < n; ++ i) { if(fa[i] == -1) dfs(i, edg, siz); } for(int i = 0; i < n; ++ i) cout << siz[i] << endl; }
n = int(input()) nums = list(map(int, input().split())) length = len(nums) dic = {} for i in range(length - 1, -1, -1): id = i + 1 if id in dic: dic[id] += 1 else: dic[id] = 1 if nums[i] != 0: if nums[i] in dic: dic[nums[i]] = dic[nums[i]] + dic[id] else: dic[nums[i]] = dic[id] for k in sorted(dic): print(dic[k])
import java.util.*; public class Main{ static int[]size; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n=in.nextInt(); List<List<Integer>>graph=new ArrayList<>(n+1); graph.add(null); for(int i=0;i<n;i++)graph.add(new ArrayList<>()); Set<Integer>set=new HashSet<>(); for(int i=0;i<n;i++){ int target=in.nextInt(); int cur=i+1; if(target>0){ graph.get(cur).add(target); graph.get(target).add(cur); }else{ set.add(cur); } } size=new int[n+1]; for (Integer root : set) { dfs(graph,root,-1); } for(int i=1;i<=n;i++){ System.out.println(size[i]); } } private static int dfs(List<List<Integer>>graph,int root,int parent){ int ret=0; for (Integer child : graph.get(root)) { if(child==parent)continue; ret+=dfs(graph,child,root); } size[root]=ret+1; return ret+1; } }
#include<iostream> #include<vector> using namespace std; void func(){ int n; cin>>n; vector<int> A(n+1); vector<int> num(n+1,1); for(int i=1;i<=n;i++){ cin>>A[i]; } for(int i=n;i>=1;i--){ num[A[i]] += num[i]; } for(int i=1;i<=n;i++){ cout<<num[i]<<endl; } } int main(){ func(); return 0; }