Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- const int MAXN = 1e5 + 10;
- const int MAXK = 21;
- array<array<int, MAXK>, MAXN> dp;
- array<vector<int>, MAXN> grafo;
- array<int, MAXN> prof;
- void dfs(int v, int p)
- {
- prof[v] = prof[p]+1;
- dp[v][0] = p;
- for (int k = 1; k < MAXK; k++) dp[v][k] = dp[dp[v][k-1]][k-1];
- for (auto viz : grafo[v])
- {
- if (viz == p) continue;
- dfs(viz, v);
- }
- }
- int lca(int x, int y)
- {
- if (prof[x] < prof[y]) swap(x, y);
- int D = prof[x] - prof[y];
- for (int k = 0; k < MAXK; k++)
- if (D & (1 << k)) x = dp[x][k];
- if (x == y) return x;
- for (int k = MAXK-1; k >= 0; k--)
- if (dp[x][k] != dp[y][k])
- x = dp[x][k], y = dp[y][k];
- return dp[x][0];
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N;
- cin >> N;
- vector<pair<int, int>> edges(N);
- for (auto &[x, y] : edges)
- {
- cin >> x >> y;
- grafo[x].push_back(y);
- grafo[y].push_back(x);
- }
- dfs(1, 1);
- vector<tuple<int, int, int, int>> queries(N);
- for (int i = 1; i < N; i++)
- {
- int X;
- cin >> X;
- queries[i-1] = make_tuple(i, i+1, lca(i, i+1), X);
- }
- vector<int> x(N+1); x[1] = 0;
- for (int m = 2; m <= (int)1e12; m *= 2)
- {
- for (auto [a, b, l, X] : queries)
- {
- x[b] = (X % m) + ((2 * x[l]) % m) - (x[a] % m);
- x[b] = ((x[b] % m) + m) % m;
- }
- }
- vector<int> resp;
- for (auto [X, Y] : edges)
- {
- if (prof[X] < prof[Y]) swap(X, Y);
- resp.push_back(x[X] - x[Y]);
- if (resp.back() <= 0) {cout << -1 << '\n'; return 0;}
- }
- for (auto X : resp) cout << X << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
