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 |
|
|
|
|
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 |