AtCoder ABC #312 (ユニークビジョンプログラミングコンテスト2023 夏) : G - Avoid Straight Line

久々に初心者向けの難易度。
https://atcoder.jp/contests/abc312/tasks/abc312_g

問題

木を成す無向グラフが与えられる。
以下を満たす頂点の組(i,j,k)は何通りか。

• i,j,kを含む単純パスは存在しない。

解法

条件を満たす(i,j,k)においては、以下のような頂点vが1つ存在する。

• v-iとv-jとv-kのパスは、v以外に共通点を持たない。

vを総当たりすることを考える。
vを根頂点と考えたとき、i,j,kが異なる子頂点のSubTreeにあればよい。
これは、各子頂点のSubTreeのサイズがわかれば計算できる。

int N;
vector<int> E[202020];
ll ret;
int C[202020];
int dfs(int cur,int pre) {
	C[cur]=1;
	vector<int> V;
	FORR(e,E[cur]) if(e!=pre) {
		V.push_back(dfs(e,cur));
		C[cur]+=V.back();
	}
	V.push_back(N-C[cur]);
	ll from[3]={0,0,0};
	FORR(v,V) {
		ll to[3]={0,0,0};
		ret+=from[2]*v;
		to[2]=from[2]+from[1]*v;
		to[1]=from[1]+v;
		swap(from,to);
	}
	return C[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	cout<<ret<<endl;
}

まとめ

いつもならFで出てもおかしくないね。