[toph.co] Interesting Triplets (Hard)

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Interesting Triplets (Hard)
Source            : toph.co
Category          : Graph Theory, Tree
Algorithm         : Tree, DFS
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll           long long
 
static const int maxn = 1e5 + 5;
 
vector <int> graph[maxn];
int tnode, subtreesize[maxn];
ll ans;
 
inline void dfs(int u = 1, int p = -1)
{
	subtreesize[u] = 1;
	for (int v : graph[u])
	{
		if (v == p) continue;
		dfs(v, u);
		subtreesize[u] += subtreesize[v];
	}
	ll sum = 0, triplets = 0;
	for (int v : graph[u])
	{
		int sze = subtreesize[v];
		if (v == p) sze = tnode - subtreesize[u];
		triplets += sum * sze;
		sum += sze;
	}
	ans += triplets * 2;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
	int tc;
	scanf("%d", &tc);
	for (int tcase = 1; tcase <= tc; tcase++)
	{
		scanf("%d", &tnode);
		for (int e = 1; e < tnode; e++)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			graph[u].emplace_back(v);
			graph[v].emplace_back(u);
		}
		ans = 0;
		dfs();
		printf("Case %d: %lld\n", tcase, ans);
		for (int i = 0; i < maxn; i++) graph[i].clear(), subtreesize[i] = 0;
	}
}