// PA2015, runda 3, Rozstaw szyn // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <algorithm> #include <cassert> using namespace std; int N, M; long long RES = 0LL; vector<int> R; vector<vector<int> > G; pair<int, int> GO(int v, int p=-1) { // printf("GO(%d, %d)\n", v, p); if (v<M) return make_pair(R[v], R[v]); vector<int> T; for (auto w:G[v]) { if (p!=w) { auto r=GO(w, v); T.push_back(2*r.first); T.push_back(2*r.second+1); } } nth_element(T.begin(), T.begin()+T.size()/2, T.end()); nth_element(T.begin(), T.begin()+T.size()/2 - 1, T.begin()+T.size()/2); auto res=make_pair(T[T.size()/2 - 1]/2, T[T.size()/2]/2); for (auto it=T.begin(); it<T.begin()+T.size()/2; it++){ if ((*it)&1) RES += res.second - (*it)/2; } for (auto it=T.begin()+T.size()/2; it<T.end(); it++){ if (!((*it)&1)) RES += (*it)/2 - res.second; } return res; } int main() { scanf("%d%d", &N, &M); R.resize(M); G.resize(N); for (int i=1; i<N; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; G[a].push_back(b); G[b].push_back(a); } for (auto &r:R) { scanf("%d", &r); } if (N==M) { printf("0\n"); return 0; } GO(M); printf("%lld\n", RES); 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 | // PA2015, runda 3, Rozstaw szyn // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <algorithm> #include <cassert> using namespace std; int N, M; long long RES = 0LL; vector<int> R; vector<vector<int> > G; pair<int, int> GO(int v, int p=-1) { // printf("GO(%d, %d)\n", v, p); if (v<M) return make_pair(R[v], R[v]); vector<int> T; for (auto w:G[v]) { if (p!=w) { auto r=GO(w, v); T.push_back(2*r.first); T.push_back(2*r.second+1); } } nth_element(T.begin(), T.begin()+T.size()/2, T.end()); nth_element(T.begin(), T.begin()+T.size()/2 - 1, T.begin()+T.size()/2); auto res=make_pair(T[T.size()/2 - 1]/2, T[T.size()/2]/2); for (auto it=T.begin(); it<T.begin()+T.size()/2; it++){ if ((*it)&1) RES += res.second - (*it)/2; } for (auto it=T.begin()+T.size()/2; it<T.end(); it++){ if (!((*it)&1)) RES += (*it)/2 - res.second; } return res; } int main() { scanf("%d%d", &N, &M); R.resize(M); G.resize(N); for (int i=1; i<N; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; G[a].push_back(b); G[b].push_back(a); } for (auto &r:R) { scanf("%d", &r); } if (N==M) { printf("0\n"); return 0; } GO(M); printf("%lld\n", RES); return 0; } |