1026 | 2022. 02. 25 07:55:02 | Szin Attila | Útadó | cpp14 | Elfogadva 50/50 | 68ms | 25192 KiB |
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;
const ll maxN = 2e5 + 5;
const ll MOD = 1e9 + 7;
ll n;
vector<vector<ll> > g;
vector<ll> v, cnt;
vector<pair<ll, pair<ll, ll> > > mo;
ll count(ll x, ll p) {
ll ret = 1;
for(ll sz : g[x]) {
if(sz == p) continue;
ret += count(sz, x);
}
return cnt[x] = ret;
}
void solve(ll x, ll p) {
for(ll sz : g[x]) {
if(sz == p) continue;
mo.push_back({cnt[sz] * (n-cnt[sz]), {sz, x}});
solve(sz, x);
}
}
int main() {
InTheNameOfGod;
cin >> n;
g.resize(n+1);
v.resize(n-1);
cnt.resize(n+1);
for(ll i = 0; i < n-1; i++) {
ll x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(ll &i : v) cin >> i;
count(1, -1);
solve(1, -1);
sort(v.begin(), v.end());
sort(mo.begin(), mo.end());
ll ki = 0;
for(ll i = 0; i < n-1; i++) {
ki += mo[i].first * v[i] * 2;
ki %= 32609;
}
cout << ki << "\n";
for(ll i = 0; i < n-1; i++) {
cout << mo[i].second.first << " " << mo[i].second.second << " " << v[i] << "\n";
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1760 KiB | |||
2 | Elfogadva | 0/0 | 32ms | 7160 KiB | |||
3 | Elfogadva | 2/2 | 1ms | 2284 KiB | |||
4 | Elfogadva | 2/2 | 1ms | 2288 KiB | |||
5 | Elfogadva | 2/2 | 1ms | 2296 KiB | |||
6 | Elfogadva | 2/2 | 1ms | 2292 KiB | |||
7 | Elfogadva | 2/2 | 1ms | 2304 KiB | |||
8 | Elfogadva | 8/8 | 57ms | 22220 KiB | |||
9 | Elfogadva | 2/2 | 2ms | 3600 KiB | |||
10 | Elfogadva | 2/2 | 2ms | 3624 KiB | |||
11 | Elfogadva | 2/2 | 2ms | 3644 KiB | |||
12 | Elfogadva | 2/2 | 2ms | 3648 KiB | |||
13 | Elfogadva | 2/2 | 2ms | 3660 KiB | |||
14 | Elfogadva | 2/2 | 61ms | 15848 KiB | |||
15 | Elfogadva | 2/2 | 65ms | 16800 KiB | |||
16 | Elfogadva | 2/2 | 68ms | 17864 KiB | |||
17 | Elfogadva | 2/2 | 65ms | 18912 KiB | |||
18 | Elfogadva | 2/2 | 63ms | 19952 KiB | |||
19 | Elfogadva | 2/2 | 59ms | 20796 KiB | |||
20 | Elfogadva | 2/2 | 63ms | 21772 KiB | |||
21 | Elfogadva | 2/2 | 68ms | 21996 KiB | |||
22 | Elfogadva | 2/2 | 64ms | 23092 KiB | |||
23 | Elfogadva | 2/2 | 57ms | 24148 KiB | |||
24 | Elfogadva | 2/2 | 65ms | 25192 KiB |