verify/codeforces/codeforces-1551F.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://codeforces.com/contest/1551/problem/F

Depends on

Code

#define PROBLEM "https://codeforces.com/contest/1551/problem/F"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/modular-arithmetic/mod-int.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;
	cin >> tt;
	for (int tc = 1; tc <= tt; ++tc) {
		int n, k;
		cin >> n >> k;
		vector<mi> fact(n + 1);
		vector<mi> ifact(n + 1);
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) {
			fact[i] = fact[i - 1] * i;
		}
		ifact[n] = 1 / fact[n];
		for (int i = n - 1; i >= 0; --i) {
			ifact[i] = ifact[i + 1] * (i + 1);
		}
		auto C = [&](int x, int y) {
		};
		vector<vector<int>> g(n);
		for (int i = 0; i < n - 1; ++i) {
			int u, v;
			cin >> u >> v;
			--u, --v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		if (k == 2) {
			cout << n * (n - 1) / 2 << '\n';
			continue;
		}
		mi ans = 0;
		for (int r = 0; r < n; ++r) {
			vector<vector<int>> store(n);
			vector<int> dep(n);
			function<void(int, int, int)> dfs = [&](int u, int p, int s) {
				++store[dep[u]].back();
				for (int v : g[u]) {
					if (v != p) {
						dep[v] = dep[u] + 1;
						dfs(v, u, s);
					}
				}
			};
			for (int u : g[r]) {
				for (int i = 0; i < n; ++i) {
					store[i].push_back(0);
				}
				dep[u] = 1;
				dfs(u, r, u);
			}
			auto comb = [&](vector<mi> a, vector<mi> b) {
				vector<mi> res(a.size() + b.size() - 1);
				for (int i = 0; i < a.size(); ++i) {
					for (int j = 0; j < b.size(); ++j) {
						res[i + j] += a[i] * b[j];
					}
				}
				return res;
			};
			for (int d = 0; d < n; ++d) {
				vector<mi> res = {1};
				for (int x : store[d]) {
					res = comb(res, vector<mi>{1, x});
				}
				if (res.size() > k) {
					ans += res[k];
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

#define PROBLEM "https://codeforces.com/contest/1551/problem/F"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7; // 998244353


typedef std::decay<decltype(MOD)>::type mod_t; 
struct mi {
	mod_t v;
	explicit operator mod_t() const { return v; }
	explicit operator bool() const { return v != 0; }
	mi() { v = 0; }
	mi(const long long& _v) {
		v = (-MOD <= _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD; }
	friend std::istream& operator>>(std::istream& in, mi& a) { 
		long long x; std::cin >> x; a = mi(x); return in; }
	friend std::ostream& operator<<(std::ostream& os, const mi& a) { return os << a.v; }
	friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }    
	friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
	friend bool operator>(const mi& a, const mi& b) { return a.v > b.v; }
	friend bool operator<=(const mi& a, const mi& b) { return a.v <= b.v; }
	friend bool operator>=(const mi& a, const mi& b) { return a.v >= b.v; }
	mi operator-() const { return mi(-v); }
	mi& operator+=(const mi& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this; }
	mi& operator-=(const mi& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this; }
	mi& operator*=(const mi& m) { v = (long long)v * m.v % MOD;
		return *this; }
	friend mi pow(mi a, long long p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; }
	friend mi inv(const mi& a) { assert(a != 0); return pow(a, MOD - 2); }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;
	cin >> tt;
	for (int tc = 1; tc <= tt; ++tc) {
		int n, k;
		cin >> n >> k;
		vector<mi> fact(n + 1);
		vector<mi> ifact(n + 1);
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) {
			fact[i] = fact[i - 1] * i;
		}
		ifact[n] = 1 / fact[n];
		for (int i = n - 1; i >= 0; --i) {
			ifact[i] = ifact[i + 1] * (i + 1);
		}
		auto C = [&](int x, int y) {
		};
		vector<vector<int>> g(n);
		for (int i = 0; i < n - 1; ++i) {
			int u, v;
			cin >> u >> v;
			--u, --v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		if (k == 2) {
			cout << n * (n - 1) / 2 << '\n';
			continue;
		}
		mi ans = 0;
		for (int r = 0; r < n; ++r) {
			vector<vector<int>> store(n);
			vector<int> dep(n);
			function<void(int, int, int)> dfs = [&](int u, int p, int s) {
				++store[dep[u]].back();
				for (int v : g[u]) {
					if (v != p) {
						dep[v] = dep[u] + 1;
						dfs(v, u, s);
					}
				}
			};
			for (int u : g[r]) {
				for (int i = 0; i < n; ++i) {
					store[i].push_back(0);
				}
				dep[u] = 1;
				dfs(u, r, u);
			}
			auto comb = [&](vector<mi> a, vector<mi> b) {
				vector<mi> res(a.size() + b.size() - 1);
				for (int i = 0; i < a.size(); ++i) {
					for (int j = 0; j < b.size(); ++j) {
						res[i + j] += a[i] * b[j];
					}
				}
				return res;
			};
			for (int d = 0; d < n; ++d) {
				vector<mi> res = {1};
				for (int x : store[d]) {
					res = comb(res, vector<mi>{1, x});
				}
				if (res.size() > k) {
					ans += res[k];
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}