fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define INF 0x3f3f3f3f
  3. using namespace std;
  4. int dp[200010][21];
  5. vector<int> g[200010];
  6. void dfs(int u, int fa) {
  7.     int i;
  8.     for (i = 1; i <= 20; i++)
  9.         dp[u][i] = i;
  10.     for (i = 0; i < g[u].size(); i++) {
  11.         int v = g[u][i];
  12.         if (v == fa) continue;
  13.         dfs(v, u);
  14.         for (int i = 1; i <= 20; i++) {
  15.             int tmp = INF;
  16.             for (int j = 1; j <= 20; j++) {
  17.                 if (i == j) continue;
  18.                 tmp = min(tmp, dp[v][j]);
  19.             }
  20.             dp[u][i] += tmp;
  21.         }
  22.     }
  23. }
  24. int main()
  25. {
  26. int t,i,j,k,xx,n;
  27. cin>>t;
  28. for(xx=1;xx<=t;xx++)
  29. {
  30.     memset(dp,0,sizeof(dp));
  31.     memset(g, 0, sizeof(g));
  32. cin>>n;
  33. for(i=0;i<n;i++)
  34. {
  35. cin>>j;
  36. g[i+1].push_back(j);
  37. g[j].push_back(i+1);
  38. }
  39. dfs(0, -1);
  40.         int ans = INF;
  41.         for (int i = 1; i <= 20; i++)
  42.             ans = min(ans, dp[0][i]-i);
  43.         printf("Case #%d: %d\n",xx, ans);
  44. }
  45. return 0;
  46. }
  47.  
Success #stdin #stdout 0s 21848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oGmWhE
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!