9314 | 2024. 02. 20 12:39:57 | Ablablabla | Útadó | cpp17 | Hibás válasz 0/50 | 104ms | 16768 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 32609;
vector<vector<int>> csucsok;
vector<int> alatta;
int bejar(int akt, int elozo){
for(int x : csucsok[akt]){
if(x == elozo) continue;
alatta[akt] += bejar(x, akt);
}
alatta[akt]++;
return alatta[akt];
}
int main()
{
int n;
cin >> n;
int m = n - 1;
csucsok.assign(n, vector<int>());
vector<pii> elek;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--; b--;
csucsok[a].push_back(b);
csucsok[b].push_back(a);
elek.push_back({a, b});
}
alatta.assign(n, 0);
bejar(0, -1);
vector<int> adok(m);
for(int i = 0; i < m; i++){
cin >> adok[i];
adok[i] %= MOD;
}
sort(adok.begin(), adok.end(), greater<int>());
vector<pii> sor(m);
for(int i = 0; i < m; i++){
int a = alatta[elek[i].first];
int b = alatta[elek[i].second];
int lent, fent;
if(a < b){
lent = a;
fent = n - a;
} else{
lent = b;
fent = n - b;
}
sor[i] = {lent * fent, i};
}
ll valasz = 0;
sort(sor.begin(), sor.end(), greater<pii>());
for(int i = 0; i < m; i++){
valasz += sor[i].first * adok[i];
valasz %= MOD;
}
cout << (valasz * 2) % MOD << "\n";
for(int i = 0; i < m; i++){
cout << elek[sor[i].second].first + 1 << " " << elek[sor[i].second].second + 1 << " " << adok[i] << "\n";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 0/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1812 KiB | |||
2 | Hibás válasz | 0/0 | 39ms | 5496 KiB | |||
3 | Hibás válasz | 0/2 | 3ms | 2680 KiB | |||
4 | Hibás válasz | 0/2 | 3ms | 2856 KiB | |||
5 | Hibás válasz | 0/2 | 3ms | 3068 KiB | |||
6 | Hibás válasz | 0/2 | 3ms | 3156 KiB | |||
7 | Hibás válasz | 0/2 | 3ms | 3292 KiB | |||
8 | Hibás válasz | 0/8 | 97ms | 16768 KiB | |||
9 | Hibás válasz | 0/2 | 4ms | 4752 KiB | |||
10 | Hibás válasz | 0/2 | 4ms | 4728 KiB | |||
11 | Hibás válasz | 0/2 | 4ms | 4744 KiB | |||
12 | Hibás válasz | 0/2 | 4ms | 4764 KiB | |||
13 | Hibás válasz | 0/2 | 4ms | 4788 KiB | |||
14 | Hibás válasz | 0/2 | 98ms | 13556 KiB | |||
15 | Hibás válasz | 0/2 | 104ms | 14672 KiB | |||
16 | Hibás válasz | 0/2 | 98ms | 15668 KiB | |||
17 | Hibás válasz | 0/2 | 97ms | 15764 KiB | |||
18 | Hibás válasz | 0/2 | 97ms | 15900 KiB | |||
19 | Hibás válasz | 0/2 | 97ms | 15936 KiB | |||
20 | Hibás válasz | 0/2 | 98ms | 16068 KiB | |||
21 | Hibás válasz | 0/2 | 98ms | 16284 KiB | |||
22 | Hibás válasz | 0/2 | 100ms | 16288 KiB | |||
23 | Hibás válasz | 0/2 | 98ms | 16248 KiB | |||
24 | Hibás válasz | 0/2 | 101ms | 16244 KiB |