Madoka and Ladder Decomposition Codechef Solution

by

Madoka and Ladder Decomposition Codechef Solution

Madoka was given a tree on her coming of age, and not a simple one, but a rooted tree of nn vertices with a root at the vertex with the number 11.

For all i≥2i≥2, let PiPi (1≤Pi≤i−11≤Pi≤i−1) be the parent of the vertex ii.

Let’s define the depth array hh as follows: h1=1h1=1, and hi=hPi+1hi=hPi+1 for all i≥2i≥2.

The subtree of a vertex uu, denoted S(u)S(u), is defined as the set of vertices vv such that the unique path from 11 to vv contains uu. Also, we definevalu=max{h(v):v∈S(u)}.valu=max{h(v):v∈S(u)}.

A tree is divided into paths by a ladder decomposition if each vertex is located on exactly one path, and each vertex uu with at least one child lies in the same path as its child vv with the maximum valvvalv, and if there are several such vertices, then the vertex with the minimum number is selected.

Madoka defines the beauty of a tree in the following way. Let the ladder decomposition of the path lengths be L1,…,LkL1,…,Lk, then the beauty of the tree is L21+L22+⋯+L2kL12+L22+⋯+Lk2

For each ii (1≤i≤n1≤i≤n), your task is to calculate the beauty of the tree formed by the first ii vertices.

See Also : July Long Challenge 2021 Solutions Codechef

Input

  • The first line contains an integer TT – the number of test cases. Then TT test cases follow.
  • The first line of each test case contains a single integer nn – the size of the tree.
  • The second line contains n−1n−1 integers P2,…,PnP2,…,Pn.

Output

For each test case, print in a separate line a single integer – the answer to the problem.

Constraints

  • 1≤T≤101≤T≤10
  • 2≤n≤8⋅1052≤n≤8⋅105
  • 1≤Pi<i1≤Pi<i for all 2≤i≤n2≤i≤n
  • The sum of nn over all test cases is at most 8⋅1058⋅105

Subtasks

  • Subtask 1 (10 points):
    • The sum of nn is at most 2⋅1032⋅103.
    • The time limit is 11 second.
  • Subtask 2 (20 points):
    • hi≤3hi≤3 for all ii.
    • The sum of nn is at most 105105.
    • The time limit is 11 second.
  • Subtask 3 (50 points):
    • The sum of nn is at most 2⋅1052⋅105.
    • The time limit is 11 second.
  • Subtask 4 (20 points):
    • Original constraints.
    • The time limit is 2.22.2 seconds.

Sample Input

2
6
1 2 1 4 3
12
1 2 1 4 4 6 2 8 5 6 11

Sample Output

0 1 4 4 5 10
0 1 4 4 5 5 10 10 13 14 14 21

Explanation

Madoka and Ladder Decomposition Codechef Solution

Solution

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

#define int long long
#define mm(lamb, tttt) memset(lamb, tttt, sizeof lamb)
#define sz(a) (int)a.size()
#define mod 1000000007
#define debn(x) cout<<#x<<'='<<x<<endl
#define deb(x) cout<<#x<<'='<<x<<' '
#define deb2(x,y) cout<<#x <<'='<<x<<' ' <<#y<<'='<<y<<' '
#define deb2n(x,y) cout<<#x <<'='<<x<<' ' <<#y<<'='<<y<<endl 
#define deb3(x,y,z) cout<<#x <<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<' ' 
#define deb3n(x,y,z) cout<<#x <<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<endl 
#define in(ar,n) for(int i=0;i<(int)n;i++)cin>>ar[i];
#define out(ar,n) cout<<#ar<<endl; for(int i=0;i<(int)n;i++) cout<<i+1<<"-("<<ar[i+1]<<"),"; cout<<endl;
#define ub upper_bound
#define lb lower_bound
#define prt(s)  cout<<"s" 
#define prtn(s)  cout<<"s"<<endl 
#define khtm cout<<endl 
#define pb push_back
#define pf push_front
#define F first
#define S second
#define asc(a) sort(a.begin(),a.end())
#define desc(a) sort(a.begin(),a.end(),greater <int> ())
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef map <int,int> mii;
typedef set <int> si;
typedef set <char> sc;
typedef vector <int> vi;
typedef vector <string> vs;
typedef vector<vi> vvi;
typedef pair <int, int> pii;
typedef pair<int, pair<int,int> > piii;
typedef vector<pii> vii;

void dfs(vvi &adj,int src,int par,int des,vi &dep)
{
    int lev=0;
    if(adj[src].size()==1)
    {
        lev=1;
    }
    for(int I: adj[src])
    {
        if(I!=par)
        {
            if(dep[I]==-1)
            {
                dfs(adj,I,src,des,dep);
            }
            lev=max(lev,dep[I]+1);
        }
    }
    for(int I: adj[src])
    {
        if(I!=par)
        {
            if(dep[I]==lev-1)
            {dep[I]=0;break;}
        }
    }
    dep[src]=lev;
    return;
}

int32_t main()
{ 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int testcases;
    cin >> testcases;
    while(testcases--)
    {
         int n,q; cin >> n;
         vvi adj(n+1);
         vi anss(1);
         for(int i=0;i<n-1;i++){
            int ss;  cin>>ss;
            adj[ss].pb(i+2);
            adj[i+2].pb(ss);
            vi depth(n+1,-1);
            dfs(adj,1,0,0,depth);
            int ans=0;
            for(int j=0;j<i+2;j++)
            {
                if(depth[j+1]>0)
                ans+=(depth[j+1]-1)*(depth[j+1]-1);
            }
            anss.pb(ans);
     
         }
         for(int I: anss)
         cout<<I<<' ';
         khtm;

    }
}

July Long Challenge 2021 Solutions

Weekly Contest 247

Biweekly Contest 55

Leave a Comment

3 + fifteen =