#include <bits/stdc++.h> #define MP make_pair #define PB push_back #define int long long #define st first #define nd second #define rd third #define FOR(i, a, b) for(int i =(a); i <=(b); ++i) #define RE(i, n) FOR(i, 1, n) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REP(i, n) for(int i = 0;i <(n); ++i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #ifdef LOCAL #define debug(x) {cerr <<#x<<" = " <<x<<"\n"; } #define debug2(x, y) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<"\n";} #define debug3(x, y, z) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";} #define debug4(x, y, z, t) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<", "<<#t <<" = " <<t<<"\n";} #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }} #else #define debug(x) #define debug2(x, y) #define debug3(x, y, z) #define debug4(x,y,z,t) #define debugv(x) #define cerr if(0)cout #endif #define make(type, x) type x; cin>>x; #define make2(type, x, y) type x, y; cin>>x>>y; #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z; #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t; #define next ____next #define prev ____prev #define left ____left #define hash ____hash using namespace std; typedef long long ll; typedef long double LD; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VLL; typedef vector<pair<int, int> > VPII; typedef vector<pair<ll, ll> > VPLL; template<class C> void mini(C&a4, C b4){a4=min(a4, b4); } template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); } template<class T1, class T2> ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";} template<class A, class B, class C> struct Triple { A first; B second; C third; bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } }; template<class T> void ResizeVec(T&, vector<int>) {} template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) { vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; } for (T& v : vec) { ResizeVec(v, sz); } } typedef Triple<int, int, int> TIII; template<class A, class B, class C> ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; } struct Res { int l, r, c; }; const int N = 5e5 + 5; VI slo[N]; bool vis[N]; Res res[N]; int roz[N]; void Dfs(int v) { vis[v] = 1; VPII ints; VI adds{0, N}; for (auto nei : slo[v]) { if (vis[nei]) { continue; } Dfs(nei); ints.PB({res[nei].l, res[nei].r}); adds.PB(res[nei].l); adds.PB(res[nei].r); res[v].c += res[nei].c; } sort(ALL(adds)); res[v].l = adds[SZ(adds) / 2 - 1]; res[v].r = adds[SZ(adds) / 2]; if (roz[v]) { res[v].l = res[v].r = roz[v]; } for (auto inter : ints) { if (res[v].l < inter.st) { res[v].c += inter.st - res[v].l; } else if (res[v].l > inter.nd) { res[v].c += res[v].l - inter.nd; } } } #undef int int main() { #define int long long ios_base::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); cin.tie(0); //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC; make2(int, n, m); RE (i, n - 1) { make2(int, a, b); slo[a].PB(b); slo[b].PB(a); } RE (i, m) { cin>>roz[i]; } Dfs(1); cout<<res[1].c<<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 117 118 119 120 121 122 | #include <bits/stdc++.h> #define MP make_pair #define PB push_back #define int long long #define st first #define nd second #define rd third #define FOR(i, a, b) for(int i =(a); i <=(b); ++i) #define RE(i, n) FOR(i, 1, n) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REP(i, n) for(int i = 0;i <(n); ++i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #ifdef LOCAL #define debug(x) {cerr <<#x<<" = " <<x<<"\n"; } #define debug2(x, y) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<"\n";} #define debug3(x, y, z) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";} #define debug4(x, y, z, t) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<", "<<#t <<" = " <<t<<"\n";} #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }} #else #define debug(x) #define debug2(x, y) #define debug3(x, y, z) #define debug4(x,y,z,t) #define debugv(x) #define cerr if(0)cout #endif #define make(type, x) type x; cin>>x; #define make2(type, x, y) type x, y; cin>>x>>y; #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z; #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t; #define next ____next #define prev ____prev #define left ____left #define hash ____hash using namespace std; typedef long long ll; typedef long double LD; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VLL; typedef vector<pair<int, int> > VPII; typedef vector<pair<ll, ll> > VPLL; template<class C> void mini(C&a4, C b4){a4=min(a4, b4); } template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); } template<class T1, class T2> ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";} template<class A, class B, class C> struct Triple { A first; B second; C third; bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } }; template<class T> void ResizeVec(T&, vector<int>) {} template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) { vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; } for (T& v : vec) { ResizeVec(v, sz); } } typedef Triple<int, int, int> TIII; template<class A, class B, class C> ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; } struct Res { int l, r, c; }; const int N = 5e5 + 5; VI slo[N]; bool vis[N]; Res res[N]; int roz[N]; void Dfs(int v) { vis[v] = 1; VPII ints; VI adds{0, N}; for (auto nei : slo[v]) { if (vis[nei]) { continue; } Dfs(nei); ints.PB({res[nei].l, res[nei].r}); adds.PB(res[nei].l); adds.PB(res[nei].r); res[v].c += res[nei].c; } sort(ALL(adds)); res[v].l = adds[SZ(adds) / 2 - 1]; res[v].r = adds[SZ(adds) / 2]; if (roz[v]) { res[v].l = res[v].r = roz[v]; } for (auto inter : ints) { if (res[v].l < inter.st) { res[v].c += inter.st - res[v].l; } else if (res[v].l > inter.nd) { res[v].c += res[v].l - inter.nd; } } } #undef int int main() { #define int long long ios_base::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); cin.tie(0); //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC; make2(int, n, m); RE (i, n - 1) { make2(int, a, b); slo[a].PB(b); slo[b].PB(a); } RE (i, m) { cin>>roz[i]; } Dfs(1); cout<<res[1].c<<endl; return 0; } |