#include<bits/stdc++.h> #define rep(i,k,n) for(int i= (int) k;i< (int) n;i++) #define pb push_back #define ft first #define sd second typedef long long ll; const long long inf = 9223372036854775807ll; const int iinf = 2147483647; const int limit = 1048576; using namespace std; bool sync_with_stdio (bool sync = false); vector<pair<ll, ll> > segs(limit, {0, 0}); vector<vector<ll> > nei(limit); vector<bool> visited(limit); ll dfs(ll v) { visited[v] = true; if(segs[v] != make_pair(0ll, 0ll)) return 0; ll res = 0; vector<pair<ll, ll> > verts; rep(i, 0, nei[v].size()) { int w = nei[v][i]; if(!visited[w]) { res += dfs(w); verts.pb({segs[w].ft, 0}); verts.pb({segs[w].sd, 1}); } } sort(verts.begin(), verts.end()); ll c = verts.size(); segs[v] = {verts[c/2 - 1].ft, verts[c/2].ft}; rep(i, 0, c/2) if(verts[i].sd == 1) res -= verts[i].ft; rep(i, c/2, c) if(verts[i].sd == 0) res += verts[i].ft; return res; } int main(){ ll n, m; scanf("%lld%lld", &n, &m); rep(i, 0, n - 1) { ll t1, t2; scanf("%lld%lld", &t1, &t2); nei[t1].pb(t2); nei[t2].pb(t1); } rep(i, 1, m + 1) { ll t1; scanf("%lld", &t1); segs[i] = {t1, t1}; } printf("%lld\n", dfs(n)); 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 | #include<bits/stdc++.h> #define rep(i,k,n) for(int i= (int) k;i< (int) n;i++) #define pb push_back #define ft first #define sd second typedef long long ll; const long long inf = 9223372036854775807ll; const int iinf = 2147483647; const int limit = 1048576; using namespace std; bool sync_with_stdio (bool sync = false); vector<pair<ll, ll> > segs(limit, {0, 0}); vector<vector<ll> > nei(limit); vector<bool> visited(limit); ll dfs(ll v) { visited[v] = true; if(segs[v] != make_pair(0ll, 0ll)) return 0; ll res = 0; vector<pair<ll, ll> > verts; rep(i, 0, nei[v].size()) { int w = nei[v][i]; if(!visited[w]) { res += dfs(w); verts.pb({segs[w].ft, 0}); verts.pb({segs[w].sd, 1}); } } sort(verts.begin(), verts.end()); ll c = verts.size(); segs[v] = {verts[c/2 - 1].ft, verts[c/2].ft}; rep(i, 0, c/2) if(verts[i].sd == 1) res -= verts[i].ft; rep(i, c/2, c) if(verts[i].sd == 0) res += verts[i].ft; return res; } int main(){ ll n, m; scanf("%lld%lld", &n, &m); rep(i, 0, n - 1) { ll t1, t2; scanf("%lld%lld", &t1, &t2); nei[t1].pb(t2); nei[t2].pb(t1); } rep(i, 1, m + 1) { ll t1; scanf("%lld", &t1); segs[i] = {t1, t1}; } printf("%lld\n", dfs(n)); return 0; } |