4300 2023-03-22 14:51:00 horvathabel Útadó cpp17 Hibás válasz 0/50 800ms 8924 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> g[50001];
vector<ll>c(50001);
vector<pair<ll,int>> db ;
ll dfs(int x){
if (c[x]==0){
db[x]={1,x};
return db[x].first;
}
else{
for (int edge:g[x]){
db[x].first+=dfs(edge);
db[x].second=x;
}
}
return (db[x].first);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;

vector<int> p;
p.resize(n+1);
for (int i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
db.assign(n+1, {1,0});
c[x]++;
p[y]=x;
g[x].push_back(y);

}
vector<ll> arak;
for (int i=1; i<n;i++){
ll x;
cin>>x;
x=x%32609;
arak.push_back(x);
}

dfs(1);
for (int i=1; i<=n;i++) db[i].first=db[i].first*(n-db[i].first)%32609;
sort(db.begin(), db.end());
sort(arak.begin(), arak.end());
ll ans=0;
vector<pair<pair<ll, ll>,ll>> cnt;
for (int i=2; i<=n;i++){
ans+=db[i].first*arak[i-2]*2;
ans=ans%32609;
cnt.push_back({{db[i].second, p[db[i].second]},arak[i-2]});
}
cout<<ans<<endl;
for (auto x: cnt) cout<<x.first.second<<" "<<x.first.first<<" "<<x.second<<endl;

}