#include <bits/stdc++.h>
using namespace std;
#define int long long
struct adat {
int a, b, c, d, e;
};
const int MOD = 32609;
const int mxN = 1e5+1;
vector<vector<int> > adj;
vector<pair<int, int> > suly(mxN);
vector<adat> ans;
int n;
bool rendez(adat x, adat y) {
if (x.e > y.e) {
return true;
}
return false;
}
int dfs(int v, int p) {
suly[v].first = 0;
suly[v].second = 0;
int cnt = 0;
for(int u : adj[v]) {
if (u != p) {
if (cnt == 0) {
suly[v].first = dfs(u, v);
cnt++;
} else if (cnt == 1) {
suly[v].second = dfs(u, v);
cnt++;
}
}
}
return suly[v].first + suly[v].second + 1;
}
void dfs2(int v, int p, int d) {
int cnt = 0;
for(int u : adj[v]) {
if(u != p) {
dfs2(u, v, cnt);
cnt++;
}
}
if (d == 0) {
ans.push_back({suly[p].first, n-suly[p].first, p, v, 0});
} else if (d == 1) {
ans.push_back({n-suly[p].second, suly[p].second, p, v, 0});
}
}
signed main() {
ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
cin >> n;
adj.resize(n+1);
for(int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, -1);
dfs2(1, 0, -1);
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
sort(v.rbegin(), v.rend());
for(auto& [x, y, z, cs, w] : ans) {
w = x * y;
w %= MOD;
}
sort(ans.begin(), ans.end(), rendez);
int anscnt = 0;
for(int i = 0; i < n-1; i++) {
anscnt += ans[i].e * v[i];
anscnt %= MOD;
}
cout << anscnt * 2 << endl;
for(int i = 0; i < n-1; i++) {
cout << ans[i].c << ' ' << ans[i].d << ' ' << v[i] << endl;
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 8/50 | ||||||
1 | Elfogadva | 0/0 | 4ms | 4788 KiB | |||
2 | Hibás válasz | 0/0 | 45ms | 10908 KiB | |||
3 | Részben helyes | 1/2 | 4ms | 5460 KiB | |||
4 | Részben helyes | 1/2 | 4ms | 5468 KiB | |||
5 | Elfogadva | 2/2 | 4ms | 5724 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 5772 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 6028 KiB | |||
8 | Hibás válasz | 0/8 | 165ms | 28980 KiB | |||
9 | Hibás válasz | 0/2 | 7ms | 7704 KiB | |||
10 | Hibás válasz | 0/2 | 7ms | 7860 KiB | |||
11 | Hibás válasz | 0/2 | 6ms | 8120 KiB | |||
12 | Hibás válasz | 0/2 | 7ms | 8240 KiB | |||
13 | Hibás válasz | 0/2 | 7ms | 8688 KiB | |||
14 | Hibás válasz | 0/2 | 155ms | 20880 KiB | |||
15 | Hibás válasz | 0/2 | 138ms | 22048 KiB | |||
16 | Hibás válasz | 0/2 | 165ms | 23316 KiB | |||
17 | Hibás válasz | 0/2 | 111ms | 24324 KiB | |||
18 | Hibás válasz | 0/2 | 108ms | 25484 KiB | |||
19 | Hibás válasz | 0/2 | 153ms | 26744 KiB | |||
20 | Hibás válasz | 0/2 | 119ms | 27752 KiB | |||
21 | Hibás válasz | 0/2 | 120ms | 28904 KiB | |||
22 | Hibás válasz | 0/2 | 118ms | 29940 KiB | |||
23 | Hibás válasz | 0/2 | 112ms | 31060 KiB | |||
24 | Hibás válasz | 0/2 | 148ms | 32108 KiB |