#include<cstdio> #include<queue> #include<algorithm> #include<vector> #include<cstring> #include<set> #include<assert.h> using namespace std; #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) #define REP(i,n) FOR(i,0,(n)-1) #define RI(i,n) FOR(i,1,n) #define pb push_back #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) bool debug; typedef vector<int> vi; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int inf = 1e9 + 5; const int nax = 5e5 + 5; bool usuniety[nax]; ll res; int n,m,a,b; int lewy[nax], prawy[nax]; vi v[nax]; priority_queue<pii> secik_min_prawy, secik_max_lewy; void dfs(int x, int f) { for (auto w: v[x]) if (w != f) { dfs(w, x); } if (x <= m) return; while (!secik_min_prawy.empty()) secik_min_prawy.pop(); while (!secik_max_lewy.empty()) secik_max_lewy.pop(); //printf("wierzcholek %d\n",x); for (auto w: v[x]) if (w != f) { //printf("przedzial %d %d\n",lewy[w], prawy[w]); secik_min_prawy.push(mp(-prawy[w], w)); secik_max_lewy.push(mp(lewy[w], w)); } lewy[x] = -1; prawy[x] = 1000000; while (!secik_min_prawy.empty()) { int l = secik_min_prawy.top().nd; int p = secik_max_lewy.top().nd; int lv = prawy[l]; int pv = lewy[p]; if (pv <= lv) { lewy[x] = max(lewy[x], pv); prawy[x] = min(prawy[x], lv); return; } else { res += pv - lv; lewy[x] = lv; prawy[x] = pv; usuniety[l] = usuniety[p] = true; } while (!secik_min_prawy.empty() && usuniety[secik_min_prawy.top().nd]) secik_min_prawy.pop(); while (!secik_max_lewy.empty() && usuniety[secik_max_lewy.top().nd]) secik_max_lewy.pop(); } } /*int psz[nax]; void przypisz(int x, int p, int f) { if (p > prawy[x]) p = prawy[x]; if (p < lewy[x]) p = lewy[x]; psz[x] = p; for (auto w: v[x]) if (w != f) { przypisz(w, p, x); } }*/ int main(int argc, char * argv[]) { debug = argc > 1; scanf("%d%d",&n,&m); REP(i,n-1) { scanf("%d%d",&a,&b); v[a].pb(b); v[b].pb(a); } FOR(i,1,m) { int x; scanf("%d",&x); lewy[i] = prawy[i] = x; } dfs(n, -1); //przypisz(n, lewy[n], -1); //ll kupa = 0; //FOR(i,1,n) for (auto w: v[i]) kupa += abs(psz[i] - psz[w]); //kupa /= 2; 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 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 | #include<cstdio> #include<queue> #include<algorithm> #include<vector> #include<cstring> #include<set> #include<assert.h> using namespace std; #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) #define REP(i,n) FOR(i,0,(n)-1) #define RI(i,n) FOR(i,1,n) #define pb push_back #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) bool debug; typedef vector<int> vi; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int inf = 1e9 + 5; const int nax = 5e5 + 5; bool usuniety[nax]; ll res; int n,m,a,b; int lewy[nax], prawy[nax]; vi v[nax]; priority_queue<pii> secik_min_prawy, secik_max_lewy; void dfs(int x, int f) { for (auto w: v[x]) if (w != f) { dfs(w, x); } if (x <= m) return; while (!secik_min_prawy.empty()) secik_min_prawy.pop(); while (!secik_max_lewy.empty()) secik_max_lewy.pop(); //printf("wierzcholek %d\n",x); for (auto w: v[x]) if (w != f) { //printf("przedzial %d %d\n",lewy[w], prawy[w]); secik_min_prawy.push(mp(-prawy[w], w)); secik_max_lewy.push(mp(lewy[w], w)); } lewy[x] = -1; prawy[x] = 1000000; while (!secik_min_prawy.empty()) { int l = secik_min_prawy.top().nd; int p = secik_max_lewy.top().nd; int lv = prawy[l]; int pv = lewy[p]; if (pv <= lv) { lewy[x] = max(lewy[x], pv); prawy[x] = min(prawy[x], lv); return; } else { res += pv - lv; lewy[x] = lv; prawy[x] = pv; usuniety[l] = usuniety[p] = true; } while (!secik_min_prawy.empty() && usuniety[secik_min_prawy.top().nd]) secik_min_prawy.pop(); while (!secik_max_lewy.empty() && usuniety[secik_max_lewy.top().nd]) secik_max_lewy.pop(); } } /*int psz[nax]; void przypisz(int x, int p, int f) { if (p > prawy[x]) p = prawy[x]; if (p < lewy[x]) p = lewy[x]; psz[x] = p; for (auto w: v[x]) if (w != f) { przypisz(w, p, x); } }*/ int main(int argc, char * argv[]) { debug = argc > 1; scanf("%d%d",&n,&m); REP(i,n-1) { scanf("%d%d",&a,&b); v[a].pb(b); v[b].pb(a); } FOR(i,1,m) { int x; scanf("%d",&x); lewy[i] = prawy[i] = x; } dfs(n, -1); //przypisz(n, lewy[n], -1); //ll kupa = 0; //FOR(i,1,n) for (auto w: v[i]) kupa += abs(psz[i] - psz[w]); //kupa /= 2; printf("%lld\n",res); return 0; } |