#include <iostream> #include <algorithm> #include <vector> #include <list> using namespace std; struct Koniec { int wart; bool czyPocz; bool operator<(const Koniec &k) const { if (wart!=k.wart) return wart<k.wart; return k.czyPocz<czyPocz; } } konce[1000000]; struct Miasto { bool jest; int lKr; list<pair<int, int> > prz; list<Miasto*> sasiedzi; Miasto() : jest(true), lKr(0) {} long long ogr(pair<int, int> &p) { int ile=prz.size(); if (ile==1) { p=*prz.begin(); return 0; } int lk=0; for (list<pair<int, int> >::iterator i=prz.begin(), k=prz.end(); i!=k; ++i) { konce[lk].czyPocz=true; konce[lk++].wart=i->first; konce[lk].czyPocz=false; konce[lk++].wart=i->second; } sort(konce, konce+lk); int zLewej=0, zPrawej=ile; for (int i=0; ; ++i) { if (konce[i].czyPocz) --zPrawej; else ++zLewej; if (zLewej==zPrawej) { p.first=konce[i].wart; p.second=konce[i+1].wart; break; } } long long wyn=0; for (list<pair<int, int> >::iterator i=prz.begin(), k=prz.end(); i!=k; ++i) { pair<int, int> &pp=*i; if (p.second<pp.first) wyn+=pp.first-p.second; else if (pp.second<p.second) wyn+=p.second-pp.second; } return wyn; } } miasta[500000]; vector<Miasto*> liscie; int main() { ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; for (int i=0; i<n-1; ++i) { int a, b; cin>>a>>b; --a; --b; ++miasta[a].lKr; ++miasta[b].lKr; miasta[a].sasiedzi.push_front(miasta+b); miasta[b].sasiedzi.push_front(miasta+a); } for (int i=0; i<m; ++i) { int r; cin>>r; liscie.push_back(miasta+i); miasta[i].prz.push_front(make_pair(r, r)); } long long wyn=0; pair<int, int> p; while (!liscie.empty()) { Miasto &lisc=*liscie.back(); liscie.pop_back(); wyn+=lisc.ogr(p); lisc.jest=false; for (list<Miasto*>::iterator i=lisc.sasiedzi.begin(), k=lisc.sasiedzi.end(); i!=k; ++i) { Miasto &sasiad=**i; if (sasiad.jest) { sasiad.prz.push_front(p); if (--sasiad.lKr==1) liscie.push_back(&sasiad); } } } cout<<wyn<<endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include <iostream> #include <algorithm> #include <vector> #include <list> using namespace std; struct Koniec { int wart; bool czyPocz; bool operator<(const Koniec &k) const { if (wart!=k.wart) return wart<k.wart; return k.czyPocz<czyPocz; } } konce[1000000]; struct Miasto { bool jest; int lKr; list<pair<int, int> > prz; list<Miasto*> sasiedzi; Miasto() : jest(true), lKr(0) {} long long ogr(pair<int, int> &p) { int ile=prz.size(); if (ile==1) { p=*prz.begin(); return 0; } int lk=0; for (list<pair<int, int> >::iterator i=prz.begin(), k=prz.end(); i!=k; ++i) { konce[lk].czyPocz=true; konce[lk++].wart=i->first; konce[lk].czyPocz=false; konce[lk++].wart=i->second; } sort(konce, konce+lk); int zLewej=0, zPrawej=ile; for (int i=0; ; ++i) { if (konce[i].czyPocz) --zPrawej; else ++zLewej; if (zLewej==zPrawej) { p.first=konce[i].wart; p.second=konce[i+1].wart; break; } } long long wyn=0; for (list<pair<int, int> >::iterator i=prz.begin(), k=prz.end(); i!=k; ++i) { pair<int, int> &pp=*i; if (p.second<pp.first) wyn+=pp.first-p.second; else if (pp.second<p.second) wyn+=p.second-pp.second; } return wyn; } } miasta[500000]; vector<Miasto*> liscie; int main() { ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; for (int i=0; i<n-1; ++i) { int a, b; cin>>a>>b; --a; --b; ++miasta[a].lKr; ++miasta[b].lKr; miasta[a].sasiedzi.push_front(miasta+b); miasta[b].sasiedzi.push_front(miasta+a); } for (int i=0; i<m; ++i) { int r; cin>>r; liscie.push_back(miasta+i); miasta[i].prz.push_front(make_pair(r, r)); } long long wyn=0; pair<int, int> p; while (!liscie.empty()) { Miasto &lisc=*liscie.back(); liscie.pop_back(); wyn+=lisc.ogr(p); lisc.jest=false; for (list<Miasto*>::iterator i=lisc.sasiedzi.begin(), k=lisc.sasiedzi.end(); i!=k; ++i) { Miasto &sasiad=**i; if (sasiad.jest) { sasiad.prz.push_front(p); if (--sasiad.lKr==1) liscie.push_back(&sasiad); } } } cout<<wyn<<endl; return 0; } |