IOICJ 77 Lowest Common Ancestor ( DFS )

Problem Description:
Node 1 denotes the root of the tree. You are given the parent nodes of 2 ~ N. Count for all v the number of ordered pairs such that their LCA is v.

Constraints:
1≤T≤100
2≤n≤100000
1≤pi

vvi G;
vl ans;

vi size;

void dfs( int u, int fa ){
  size[ u ] = 1;
  for( int v : G[ u ] ){
    if( v == fa ) continue;
    dfs( v, u );
    size[ u ] += size[ v ];
  }
}

void dfs2( int u, int fa ){
  --size[ u ];
  ans[ u ] = 1;
  for( int v : G[ u ] ){
    if( v == fa ) continue;
    ans[ u ] += 1LL * size[ v ] * ( size[ u ] - size[ v ] );
    ans[ u ] += size[ v ] * 2;
    dfs2( v, u );
  }
  ++size[ u ];
}

void solve(){
  int T; cin >> T;
  while( T-- ){
    int N; cin >> N;
    G = vvi( N );
    size = vi( N );
    ans = vl( N );
    for( int i = 1; i < N; ++i ){
      int p; cin >> p; --p;
      G[ p ].emplace_back( i );
    }
    dfs( 0, -1 );
    dfs2( 0, -1 );
    for( int i = 0; i < N; ++i ){
      cout << ans[ i ] << " \n"[ i + 1 == N ];
    }
  }
}