1 条题解

  • 0
    @ 2025-10-8 17:10:13
    #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
    上传者