1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 5e5 + 10; vector<int> G[N]; int w[N]; int L[N], R[N]; int n, m, res; void dfs(int x, int xfa) { vector<int> S; if (x <= m)return; for (auto y : G[x]) if (y != xfa) { dfs(y, x); S.push_back(L[y]), S.push_back(R[y]); } sort(S.begin(), S.end()); int sz = S.size(); if (sz & 1) L[x] = R[x] = S[sz / 2]; else L[x] = S[sz / 2 - 1], R[x] = S[sz / 2]; for (auto y : G[x]) if (y != xfa) { if (L[x] > R[y]) res += L[x] - R[y]; else if (L[x] < L[y]) res += L[y] - L[x]; else res += 0; } } signed main() { ios::sync_with_stdio(False), cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 1, a, b; i < n; i++) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } for (int i = 1; i <= m; i++) cin >> w[i], L[i] = R[i] = w[i]; if (n == 2) { cout << abs(w[1] - w[2]) << "\n"; return 0; } dfs(m + 1, 0); cout << res << "\n"; return 0; }
- 1
信息
- ID
- 5962
- 时间
- 10000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者