Submission #1361677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361677		javkhlantogs	Duathlon (APIO18_duathlon)	C++20	0 / 100	1110 ms	1114112 KiB

count_triplets

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans=0;
vector<vector<ll>> e;
vector<ll> sz;
ll getsz(ll u,ll p){
	sz[u]=1;
	for(auto v:e[u]){
		if(v==p) continue;
		sz[u]+=getsz(v,u);
	}
	return sz[u];
}
void dfs(ll u,ll p){
	ans+=(sz[1]-sz[u])*(sz[u]-1);
	for(auto v:e[u]){
		if(v==p) continue;
		dfs(v,u);
	}
}
int main(){
	ll n,m,i,j,k,q;
	cin>>n>>m;
	e.resize(n+1);
	sz.resize(n+1);
	for(i=0 ; i<m ; i++){
		cin>>j>>k;
		e[j].push_back(k);
		e[k].push_back(j);
	}
	getsz(1,1);
	dfs(1,1);
	cout<<ans*2<<"\n";
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10