Contestant_. Rank 230. Rating +111 (+461 -350).不小心给sqrt传了double，爆精度被叉了一题qaq
A. Array Coloring
题意
给定一个序列，将其分成非空两堆，并给两堆数染上不同颜色。
输出是否存在一种分配方式，使两堆数总和的奇偶性相等。
题意
显然，奇偶性相同的两个数相加，得到偶数。
所以总和为偶数就存在，否则不存在。
时间复杂度：\(O(n)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb push_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int sum = 0;
for(int i=0;i<n;i++){
int x;
cin >> x;
sum += x;
}
if(sum % 2 == 0){
cout << "YES\n";
}else cout << "NO\n";
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}签到
B. Maximum Rounding
题意
给定一个数字，定义操作为选定数字的某一位，满足该位数字 \(\geq 5\)，将该位及其后面的所有数变为 \(0\)，并将前一位数字 \(+ 1\)，向上进位。
输出一次操作后，数字的最大值。
思路
因为数字长度很大，我们考虑对字符串模拟。
因为如果前面位存在操作，那么后面位的数都会变为 \(0\)。
因而，我们倒着读数字，对所有 \(a_i \geq 5\)，执行 \(a_i := 0, a_{i - 1} ++\)，并记录最前面执行操作的位置。
最后，我们从最前面执行操作的位置开始，将后面全都替换位 \(0\) 即可。
当然，注意不要输出前导零。
时间复杂度：\(O(n)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb push_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
string s;
cin >> s;
int n = s.size(), pos = inf;
s = "0" + s;
for(int i=s.size();i>0;i--){
if(s[i] >= '5'){
s[i] = '0';
s[i - 1] ++;
pos = i;
}
}
for(int i=pos;i<s.size();i++) s[i] = '0';
for(int i=0;i<=n;i++){
if(i == 0){
if(s[i] != '0') cout << s[i];
}else cout << s[i];
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}题目有点长了捏
C. Assembly via Minimums
题意
对于一个序列 \(a\)，操作为遍历所有 \(<i, j>, 1 \leq i < j \leq n\)，并将 \(\min(a_i, a_j)\) 放入新序列 \(b\) 中。
现在，给定打乱顺序后的序列 \(b\)，输出任意一个满足条件的 \(a\)。
思路
对于升序排序的 \(a\)，不难发现，每一个元素在 \(b\) 中出现的次数是 \(n, n - 1,\ldots,1\)。
那么，我们直接对 \(b\) 倒序排个序，然后输出第 \(1, 2, 4, 7, \ldots\) 个元素即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int m = n * (n - 1) / 2;
vector<int> b(m);
for(int i=0;i<m;i++) {
cin >> b[i];
}
sort(all(b));
int cnt = 0;
for(int i=n-1;i>=0;i--){
cnt += i;
cout << b[cnt - 1] << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}差点以为 \(a\) 中元素不会重复（不重复可以用 \(map\) 完成此题）
D. Strong Vertices
题意
给定两个长度相等的数组 \(a, b\)，对于两个下标 \(u, v\ (u \neq v)\)，若满足 \(a_u - a_v \geq b_u - b_v\)，那么在图中建立一条 \(u => v\) 的有向边。
定义 "强连通点" 为 满足 存在该点 到 所有其他点的有向边。
升序输出所有 "强连通点"。
思路
首先，根据建图的方式，强连通点满足的条件就是出度为 \(n - 1\)。
我们将不等式化简，得到 \(a_u - b_u \geq a_v - b_v\)。
那么，若我们设 \(c_i = a_i - b_i\)，就有 \(c_u \geq c_v\)。
也就是说，只要 \(c_u \geq c_i\) 对所有 \(i \in [1, n], i \neq u\) 成立， \(u\) 就是一个强连通点。
判断是很显然的，我们只需找出有多少个 \(c_i\) 和 \(max(c_i)\) 相等即可。
最后，不要忘记对答案序列升序排个序。
时间复杂度：\(O(n \log n)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<pii> p(n);
for(int i=0;i<n;i++) {
p[i].sc = i + 1;
cin >> p[i].fs;
}
for(int i=0;i<n;i++) {
int cur;
cin >> cur;
p[i].fs -= cur;
}
sort(all(p));
vector<int> ans;
for(int i=n-1;i>=0;i--){
if(p[i].fs == p[n-1].fs) ans.pb(p[i].sc);
else break;
}
cout << ans.size() << '\n';
sort(all(ans));
for(auto e : ans) cout << e << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}不会真的有人觉得这是正经的图论吧（
E. Power of Points
题意
给定数轴上的 \(n\) 个点 \(x_i\)。
对于某个整数 \(s\)，对 \(i \in [1, n]\)，构造线段 \([x_i, s]\)。
定义 \(f_p\) 为与坐标 \(p\) 相交的线段数量，计算对于 \(s \in \{x1, x2, \ldots, x_n\}\) 的 \(\displaystyle \sum^{10^9}_{p=1}f_p\)。
思路
我们可以将问题转化为：对于 \(s \in \{x1, x2, \ldots, x_n\}\)，计算 \(n + \sum abs(s - x_i)\)。
那么，我们不妨直接对 \(x_i\) 排序，然后对其求前缀和 \(pre\) 和后缀和 \(suf\) (其实后缀和可以直接由前缀和得到)。
那么，对于 \(s = x_p\)，\(\sum abs(s - x_i) = (s \times (p - 1) - pre_{p - 1}) + 0 + (suf_{p + 1} - s \times (n - p))\)。
时间复杂度：\(O(n)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<pii> a(n);
vector<int> sum(n + 1);
for(int i=0;i<n;i++){
cin >> a[i].fs;
a[i].sc = i;
}
sort(all(a));
for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + a[i - 1].fs;
vector<int> ans(n);
for(int i=1;i<=n;i++){
ans[a[i - 1].sc] = a[i - 1].fs * (i - 1) - sum[i - 1] + sum[n] - sum[i] - a[i - 1].fs * (n - i) + n;
}
for(auto e : ans) cout << e << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}如果去掉题面的包裹，这题比前面几题简单
F. Sum and Product
题意
给定一个序列 \(a\)，对于 \(q\) 个询问，每次给定两个数 \(x, y\)，输出二元组 \(<i, j>, 1 \leq i < j \leq n\) 的个数，满足 \(a_i + a_j = x, a_i \times a_j = y\)。
题意
我们设 \(a_i = p, a_j = q\)，将 \(x, y\) 视为常数，那么我们可以联立并化简，得到一个一元二次方程 \(p(x - p) = y\)。
也就是 \(p ^ 2 - xp + y = 0\)。
我们对考虑 \(\Delta = x ^ 2 - 4y\) 分类讨论：
\(\Delta < 0\)，答案为 \(0\)；
\(\Delta = 0\)，那么 \(p = q\)。因为下标需要满足不同，那么我们只能在所有 \(a_x = p\) 中挑选两个，也就是组合数；
\(\Delta > 0\)，那么答案就是两个值出现次数之积。
当然，因为我们需要得到正整数解，因而根据求根公式，\(\sqrt\Delta\) 为整数，\(x + \sqrt \Delta\) 为偶数。
判断的时候注意不要爆精度。
至于出现次数，使用 \(map\) 即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
template<class T> T ex_sqrt(T x) { //返回精度更高的sqrt
if(x == 0) return 0;
T sqrtX = sqrt(x) - 1;
while (sqrtX + 1 <= x / (sqrtX + 1)) sqrtX++;
return sqrtX;
}
void solve() {
int n;
cin >> n;
map<int, int> cnt;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
cnt[cur] ++;
}
int q;
cin >> q;
while(q --){
int x, y;
cin >> x >> y;
int delta = x * x - 4 * y;
if(delta < 0){
cout << 0 << ' ';
continue;
}
if(fabs(ex_sqrt(delta) * ex_sqrt(delta) - delta) > 1e-9){
cout << 0 << ' ';
continue;
}
if(abs(ex_sqrt(delta) - x) % 2 != 0){
cout << 0 << ' ';
continue;
}
int p1 = -(ex_sqrt(delta) - x) / 2, p2 = (ex_sqrt(delta) + x) / 2;
int ans = cnt[p1] * cnt[x - p1];
if(delta == 0) ans = max(0ll, cnt[p1] * (cnt[p1] - 1) / 2);
cout << ans << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}sqrt + double = 寄
G. Counting Graphs
题意
给定一颗生成树。
现在，找出满足下面条件的不同图的个数，其中边权不同即为不同：
该图的 唯一 最小生成树为给定的生成树；
不包含重边和自环
图中任意边的边权的最大值 \(S\)
思路
等价于给生成树加边，且所加边的边权应大于两点之间最短路的长度。
我们记两个点间的最短路为 \(P(u, v)\)。
显然，我们只能选择两个点进行加边，因而，如果我们假设不加边的两点加了一条虚拟的边，边权为 \(P(u, v)\)。
那么，对于每两个点，都会有一个边权的选择，选择总共有 \(S - P(u, v) + 1\) 种。
根据乘法原理，最后的答案就是 \(\prod\limits_{1\le u < v \le n}{} (S-P(u,v)+1)\)。
接下来我们考虑如何计算。
在 \(\mathtt{Kruskal}\) 算法中，我们使用了并查集来合并两个连通块。
不难发现，在合并的时候，我们可以顺便记录两个连通块分量的个数，并进行赋值，从而在每次合并前都可以快速得到左右两个连通块分量个数。
那么，在合并入一个新的连通块的时候，我们会用一条边连结。我们设两个连通块分量个数为 \(siz_u, siz_v\)，经过这条边的路径数就是 \(siz_u \times siz_v\)，减掉 \(u - v\) 这条边，剩余的路径数就是满足 \(P(a, b) = w_{u, v}\) 的所有 \(<a, b>\)。
因而，在合并的时候，我们将答案乘上 \((S - w + 1) ^ {siz_u \times siz_v - 1}\)。
如上，跑一遍 \(\mathtt{Kruskal}\) 即可。
时间复杂度：\(O(m \log m)\)
对应AC代码
//Code template from Floating Ocean.
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e3 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
struct MATH {
private:
struct PRIME {
int Check_Num = 0, Max_Factor = 0;
vector<pii> Dec;
private:
void Get_Fac(int Num) { //寻找 Num 的最大因子
if (Num <= Max_Factor || Num < 2) return;
if (Miller_Rabin(Num)) return void(Max_Factor = max(Max_Factor, Num));
int Fac = Num;
while (Fac >= Num) Fac = Pollard_Rho(Num);//寻 找 因 子
while (!(Num % Fac)) Num /= Fac;
return Get_Fac(Num), Get_Fac(Fac);
}
void Decomposition(int Num) { // 分解 Num 的质因子
if (Num < 2) return;
if (Miller_Rabin(Num)) {
pair<int, int> Now = {Num, 0};
while (Check_Num % Num == 0) Now.second++, Check_Num /= Num;
if (Now.second) Dec.pb(Now);
return;
}
int Fac = Num;
while (Fac >= Num) Fac = Pollard_Rho(Num);//寻 找 因 子
while (!(Num % Fac)) Num /= Fac;
return Decomposition(Num), Decomposition(Fac);
}
public:
__int128 test[16] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 61, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(__int128 P) { //检测 P 是不是质数, 严格保证答案正确
if (P < 3 || P % 2 == 0) return P == 2;
static int i, j;
static __int128 Tem, k, Next;
Tem = P - 1, k = 0;
while (Tem % 2 == 0) Tem >>= 1, ++k;
for (j = 1; j <= 15; j++) {
Next = qp(test[j], Tem, P);
if (Next <= 1 || Next == P - 1) continue;
for (i = 0; i < k; ++i) {
Next = Next * Next % P;
if (Next == P - 1 && i != k - 1) {
Next = 1;
break;
}
if (Next == 1) return false;
}
if (Next != 1) return false;
}
return true;
}
static bool RMiller_Rabin(__int128 P, int test_time = 8) { //检测 P 是不是质数, 基于随机检验
if (P < 3 || P % 2 == 0) return P == 2;
static int i, j;
static __int128 Tem, k, Rand_Num, Now;
Tem = P - 1, k = 0;
while (Tem % 2 == 0) Tem >>= 1, ++k;
for (i = 1; i <= test_time; ++i) {
Rand_Num = rand() % (P - 2) + 2, Now = qp(Rand_Num, Tem, P);
if (Now == 1) continue;
for (j = 0; j < k; ++j) {
if (Now == P - 1) break;
Now = Now * Now % P;
}
if (j >= k) return false;
}
return true;
}
static int Pollard_Rho(int x) {
static int s, t, c, Div, Val;
Val = 1, s = t = 0;
static int Step, Goal;
Step = 0, Goal = 1;
c = (int) rand() % (x - 1) + 1;
for (Goal = 1;; Goal <<= 1, s = t, Val = 1) { // 倍增优化
for (Step = 1; Step <= Goal; ++Step) {
t = ((__int128) t * t + c) % x, Val = (__int128) Val * abs(t - s) % x;
if (!(Step % 127)) {
Div = __gcd(Val, x);
if (Div > 1) return Div;
}
}
Div = __gcd(Val, x);
if (Div > 1) return Div;
}
}
void Get_Max_Fac(int Num) { return Max_Factor = 0, Get_Fac(Num); } //获得 Num 的最大因子 测 试: Luogu P4718
void Dec_Factor(int Num) { return Dec.clear(), Check_Num = Num, Decomposition(Num); } //分解 Num 的本质不同质因子 测 试: Prime Land
int Get_Phi(int Num) { //计算 φ(Num)
if (Num == 1) return 0;
Dec_Factor(Num);
for (auto &Now: Dec) Num = Num / Now.first * (Now.first - 1);
return Num;
}
}pm;
public:
static __int128 qp(__int128 x, __int128 y, __int128 m = mod) {
static __int128 ans;
ans = 1, x %= m;
for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
return ans;
}
//ax+by=gcd(a,b),返回gcd
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = x; x = y; y = t - (a / b) * y;
return d;
}
//x (mod Mi) = Ai
int exCRT(int n, int M[], int A[]) {
int a = A[1], m = M[1], ta, tm, x, y, d, l, t;
for (int i = 2; i <= n; i++) {
tm = M[i], ta = A[i];
d = exgcd(m, tm, x, y);
l = m * tm / d;
if ((ta - a) % d != 0) return -1;
t = tm / d;
x *= ((ta - a) / d);
x = (x % t + t) % t;
a += m * x;
m = l;
}
return a;
}
//欧拉函数，小于等于n和n互质的数的个数
int phi(int n) {
return pm.Get_Phi(n);
}
bool vis[N];
int pri[N], cnt;
//线性筛
void linear_prime(int n) {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[cnt++] = i;
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] > n) break;
vis[i * pri[j]] = true;
if (i % pri[j] == 0)break;
}
}
}
int inv_ex(int n, int m = mod) {
int x, y, ans = exgcd(n, m, x, y);
if (ans == 1) return (x % m + m) % m;
else return -1;
}
int inv(int n, int m = mod) { return qp(n, m - 2, m); }
//p为1e5以内质数，求c(n, m) % p
int lucas(int n, int m, int p) {
if (m == 0) return 1;
return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}
int C(int m, int n, int p) {
int a = 1, b = 1;
if (m < n) return 0;
while (n) {
a = (a * m) % p, b = (b * n) % p;
m--, n--;
}
return a * inv_ex(b, p) % p;
}
void get_phi(int n, int phi[]) {
for (int i = 0; i <= n; i++) phi[i] = i;
for (int i = 2; i <= n; i++)
if (phi[i] == i) for (int j = 2; j <= n; j++) phi[j] = phi[j] / i * (i - 1);
}
//线性求逆元
void get_inv(int n, int inv[], int p = mod) {
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = inv[i] = (p - p / i * inv[p % i] % p) % p;
}
//线性求阶乘，逆元，阶乘逆元
void get_fact_inv(int n, int fac[], int Inv[], int fac_inv[], int p = mod) {
fac[0] = fac_inv[0] = Inv[0] = fac[1] = fac_inv[1] = Inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % p;
Inv[i] = (p - p / i * Inv[p % i] % p) % p;
fac_inv[i] = fac_inv[i - 1] * Inv[i] % p;
}
}
vector<pii> factorize(int x) { return pm.Dec_Factor(x), pm.Dec; }
int max_factor(int x){ return pm.Get_Max_Fac(x), pm.Max_Factor; }
void miller_rabin(__int128 P){ pm.Miller_Rabin(P); }
void random_miller_rabin(__int128 P, int test_time = 8){ pm.RMiller_Rabin(P, test_time); }
int pollard_pho(int x) { pm.Pollard_Rho(x); }
template<class T> T ex_sqrt(T x) { //返回精度更高的sqrt
T sqrtX = sqrt(x) - 1;
while (sqrtX + 1 <= x / (sqrtX + 1)) sqrtX++;
return sqrtX;
}
}math;
struct DSU {
vector<int> pa;
void init(int n) { pa = vector<int>(n + 1), iota(all(pa), 0); }
int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
void unite(int u, int v) {
int f1 = find(u);
int f2 = find(v);
if (f1 != f2) pa[f2] = f1;
}
}dsu;
struct KRUSKAL {
int n, m, idx;
struct Edge{
int a, b, w;
bool operator< (const Edge &W)const{ return w < W.w; }
}edges[M];
void init(int tn, int tm){ n = tn, m = tm, dsu.init(n), idx = 0; }
void add(int u, int v, int w) { edges[idx ++] = {u, v, w}; }
int kruskal(auto func){
sort(edges, edges + m);
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++){
auto [a, b, w] = edges[i];
a = dsu.find(a), b = dsu.find(b);
if (a != b) dsu.unite(a, b), res += w, cnt ++;
func(a, b, w);
}
if (cnt < n - 1) return inf;
return res;
}
}kruskal;
void solve() {
int n;
cin >> n;
vector<int> siz(n + 1, 1);
kruskal.init(n, n - 1);
int s;
cin >> s;
for(int i=0;i<n-1;i++){
int u, v, w;
cin >> u >> v >> w;
kruskal.add(u, v, w);
}
int ans = 1;
kruskal.kruskal([&](int tx, int ty, int w) -> void{
ans = ans * math.qp(s - w + 1, siz[tx] * siz[ty] - 1, mod) % mod;
siz[tx] += siz[ty];
});
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}随手扔了个数论板子，一下子给干到200行了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论