Submission #3127348


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
// #define DEBUG_OUT cerr
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T, class = typename iterator_traits< typename T::iterator >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
template < class T, class = typename iterator_traits< typename T::iterator >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}


const int N = 1e5;
std::vector<int> g[N];
int n;

int sz[N];

pair<int, int> centroid(-1, -1);
ll v[N];
ll ans[N];
map<pair<int, int>, int> edge;
void dfs(int i, int p) {
  sz[i] = 1;
  for(int j : g[i]) if(j != p) {
    dfs(j, i);
    sz[i] += sz[j];
    int A = n - sz[j] - 1;
    int B = sz[j] - 1;
    if(A == B) centroid = make_pair(i, j);
    else {
      ans[edge[make_pair(min(i,j), max(i,j))]] = (v[j] - v[i]) / (A - B);
    }
  }
}

ll dfs2(int i, int p, ll x) {
  ll res = 0;
  // dump(i, x);
  for(int j : g[i]) if(j != p) {
    ll d = ans[edge[make_pair(min(i,j), max(i,j))]];
    res += x + d;
    res += dfs2(j, i, x + d);
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  for(int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    if(a > b) swap(a, b);
    edge[make_pair(a, b)] = i;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  for(int i = 0; i < n; i++) cin >> v[i];
  dfs(0, -1);
  if(centroid.first != -1) {
    int a, b; tie(a, b) = centroid;
    // dump(a, b);
    if(a > b) swap(a, b);
    ll d = dfs2(a, -1, 0);
    // dump(d);
    ans[edge[make_pair(a,b)]] = (v[a] - d) / (n / 2);
  }
  for(int i = 0; i < n - 1; i++) cout << ans[i] << endl;
  return 0;
}

Submission Info

Submission Time
Task D - Ancient Tree Record
User luma
Language C++14 (GCC 5.4.1)
Score 800
Code Size 3199 Byte
Status AC
Exec Time 295 ms
Memory 27008 KB

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 300 / 300 200 / 200 300 / 300
Status
AC × 3
AC × 14
AC × 11
AC × 48
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt
Subtask2 00_example_02.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt, s3_42.txt, s3_43.txt, s3_44.txt, s3_45.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 2 ms 2560 KB
00_example_02.txt AC 2 ms 2560 KB
00_example_03.txt AC 2 ms 2560 KB
s1_01.txt AC 138 ms 16384 KB
s1_02.txt AC 186 ms 22016 KB
s1_03.txt AC 10 ms 3456 KB
s1_04.txt AC 153 ms 18688 KB
s1_05.txt AC 25 ms 5248 KB
s1_06.txt AC 237 ms 27008 KB
s1_07.txt AC 246 ms 27008 KB
s1_08.txt AC 234 ms 27008 KB
s1_09.txt AC 2 ms 2560 KB
s1_10.txt AC 2 ms 2560 KB
s1_11.txt AC 2 ms 2560 KB
s1_12.txt AC 2 ms 2560 KB
s1_13.txt AC 2 ms 2560 KB
s2_14.txt AC 122 ms 9596 KB
s2_15.txt AC 175 ms 12536 KB
s2_16.txt AC 217 ms 15096 KB
s2_17.txt AC 218 ms 15096 KB
s2_18.txt AC 219 ms 15096 KB
s2_19.txt AC 216 ms 15096 KB
s2_20.txt AC 2 ms 2560 KB
s2_21.txt AC 2 ms 2560 KB
s2_22.txt AC 2 ms 2560 KB
s2_23.txt AC 2 ms 2560 KB
s3_24.txt AC 145 ms 9472 KB
s3_25.txt AC 210 ms 12160 KB
s3_26.txt AC 10 ms 3072 KB
s3_27.txt AC 174 ms 10496 KB
s3_28.txt AC 26 ms 3968 KB
s3_29.txt AC 268 ms 14592 KB
s3_30.txt AC 261 ms 14848 KB
s3_31.txt AC 266 ms 14592 KB
s3_32.txt AC 286 ms 21376 KB
s3_33.txt AC 264 ms 25216 KB
s3_34.txt AC 256 ms 15096 KB
s3_35.txt AC 258 ms 15096 KB
s3_36.txt AC 2 ms 2560 KB
s3_37.txt AC 2 ms 2560 KB
s3_38.txt AC 2 ms 2560 KB
s3_39.txt AC 2 ms 2560 KB
s3_40.txt AC 156 ms 9472 KB
s3_41.txt AC 229 ms 12160 KB
s3_42.txt AC 10 ms 3072 KB
s3_43.txt AC 295 ms 14592 KB
s3_44.txt AC 290 ms 14848 KB
s3_45.txt AC 293 ms 14592 KB