Submission #59378810

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> g[200005];
int dsu[200005];

inline int root(int x) {
	while (x != dsu[x])
		x = dsu[x] = dsu[dsu[x]];
	return x;
}

void dfs(int cur, int pa, int& cnt) {
	for (const auto& i : g[cur]) {
		if (g[i].size() == 2)
			cnt++;
		if (i != pa && g[i].size() == 3)
			dfs(i, cur, cnt);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1, u, v; i < n; i++)
		cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
	iota(dsu, dsu + n + 1, 0);
	for (int i = 1; i <= n; i++)
		if (g[i].size() == 3)
			for (const auto& j : g[i])
				if (g[j].size() == 3)
					if (const int ru = root(i), rv = root(j); ru != rv)
						dsu[ru] = rv;
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		if (g[i].size() == 3 && dsu[i] == i) {
			int cnt = 0;
			dfs(i, 0, cnt);
			res += 1LL * cnt * (cnt - 1) / 2;
		}
	}
	cout << res << '\n';
	return 0;
}

Submission Info

Submission Time
Task F - Add One Edge 2
User woruo27
Language C++ 17 (gcc 12.2)
Score 500
Code Size 982 Byte
Status AC
Exec Time 78 ms
Memory 18412 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 39
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 02_hand_01.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 3 ms 8100 KiB
00_sample_02.txt AC 3 ms 8120 KiB
00_sample_03.txt AC 3 ms 8064 KiB
01_test_01.txt AC 60 ms 15292 KiB
01_test_02.txt AC 78 ms 15144 KiB
01_test_03.txt AC 65 ms 15224 KiB
01_test_04.txt AC 65 ms 15296 KiB
01_test_05.txt AC 59 ms 15124 KiB
01_test_06.txt AC 68 ms 15124 KiB
01_test_07.txt AC 69 ms 15156 KiB
01_test_08.txt AC 74 ms 15228 KiB
01_test_09.txt AC 62 ms 15232 KiB
01_test_10.txt AC 62 ms 15088 KiB
01_test_11.txt AC 59 ms 15232 KiB
01_test_12.txt AC 61 ms 15092 KiB
01_test_13.txt AC 64 ms 15124 KiB
01_test_14.txt AC 73 ms 15152 KiB
01_test_15.txt AC 68 ms 15220 KiB
01_test_16.txt AC 10 ms 9240 KiB
01_test_17.txt AC 54 ms 14052 KiB
01_test_18.txt AC 13 ms 9656 KiB
01_test_19.txt AC 29 ms 11616 KiB
01_test_20.txt AC 18 ms 10324 KiB
01_test_21.txt AC 37 ms 18412 KiB
01_test_22.txt AC 37 ms 18348 KiB
01_test_23.txt AC 38 ms 18312 KiB
01_test_24.txt AC 35 ms 18344 KiB
01_test_25.txt AC 36 ms 18412 KiB
01_test_26.txt AC 57 ms 15444 KiB
01_test_27.txt AC 52 ms 15448 KiB
01_test_28.txt AC 61 ms 15344 KiB
01_test_29.txt AC 53 ms 15444 KiB
01_test_30.txt AC 55 ms 15452 KiB
01_test_31.txt AC 51 ms 15416 KiB
01_test_32.txt AC 53 ms 15352 KiB
01_test_33.txt AC 63 ms 15368 KiB
01_test_34.txt AC 59 ms 15428 KiB
01_test_35.txt AC 67 ms 15316 KiB
02_hand_01.txt AC 31 ms 15148 KiB