Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #include <cstring>
- #include <bitset>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#define int ll
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("avx2")
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair < int, int > pii;
- typedef pair < ll, ll > pll;
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 2e5 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"π", "π", "π"};
- int c[N];
- vector < int > g[N];
- map < int, int > dp[N];
- int dp2[N], n, a[N];
- vector < int > order;
- void dfs(int u, int p) {
- a[u] = p;
- for (int v : g[u]) {
- if (v != p) {
- dfs(v, u);
- dp[u][v] = dp2[v];
- dp2[u] += max(0, dp2[v]);
- }
- }
- //debug(u, dp2[u]);
- if (c[u]) {
- dp2[u]++;
- }
- else {
- dp2[u]--;
- }
- order.push_back(u);
- }
- signed main() {
- //debug(true);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(4);
- ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> c[i];
- }
- for (int i = 1; i < n; i++) {
- int u, v;
- cin >> u >> v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- dfs(1, 0);
- order.pop_back();
- reverse(order.begin(), order.end());
- for (int u : order) {
- debug(u, dp2[a[u]], dp[a[u]][u]);
- dp2[u] += max(0, dp2[a[u]] - max(0, dp[a[u]][u]));
- }
- for (int i = 1; i <= n; i++) {
- cout << dp2[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement