Shawn's Blog

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1, M = 2 * N;
int n, u, v;
int a[N], h[N], e[M], ne[M], idx;
int dp[N];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    function<void(int, int)> dfs = [&](int u, int f) {
        dp[u] = a[u] ? 1 : -1;
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                dfs(v, u);
                if (dp[v] > 0) dp[u] += dp[v];
            }
        }
    };
    dfs(1, 0);
    function<void(int, int)> reroot = [&](int u, int f) {
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                int from = dp[u], to = dp[v];
                if (to > 0) from -= to;
                if (from > 0) to += from;
                dp[v] = to;
                reroot(v, u);
            }
        }
    };
    reroot(1, 0);
    for (int i = 1; i < n; ++i) printf("%d ", dp[i]);
    printf("%d\n", dp[n]);
    return 0;
}

class Solution {
public:
    int rootCount(vector<vector<int>>& edges, vector<vector<int>>& guesses, int k) {
        vector<vector<int>> g(edges.size() + 1);
        for (auto &e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        unordered_set<long> s;
        for (auto &gs : guesses) s.insert((long) gs[0] << 32 | gs[1]);
        int ans = 0, cnt0 = 0;
        function<void(int, int)> dfs = [&](int x, int f) {
            for (int y : g[x]) {
                if (y != f) {
                    cnt0 += s.count((long) x << 32 | y);
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);
        function<void(int, int, int)> reroot = [&](int x, int f, int cnt) {
            if (cnt >= k) ++ans;
            for (int y : g[x]) {
                if (y != f) {
                    reroot(y, x, cnt 
                                - s.count((long) x << 32 | y)
                                + s.count((long) y << 32 | x));
                }
            }
        };
        reroot(0, -1, cnt0);
        return ans;
    }
};

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6 + 1, M = N * 2;
int n, u, v;
int h[N], e[M], ne[M], idx, sz[N];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    int sum = 0;
    function<void(int, int, int)> dfs = [&](int f, int u, int d) {
        sz[u] = 1;
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                sum += d + 1;
                dfs(u, v, d + 1);
                sz[u] += sz[v];
            }
        }
    };
    dfs(0, 1, 0);
    int ans = 1;
    LL maxsum = sum;
    function<void(int, int, LL)> reroot = [&](int f, int u, LL us) {
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                LL vs = us - sz[v] + (n - sz[v]);
                if (maxsum < vs) maxsum = vs, ans = v;
                reroot(u, v, vs);
            }
        }
    };
    reroot(0, 1, sum);
    printf("%d\n", ans);
    return 0;
}

class Solution {
    static constexpr int DIRS[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; // downward, rightward, rotate
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int n = grid.size();
        bool st[n][n][2];
        memset(st, 0, sizeof(st));
        st[0][0][0] = 1;
        vector<tuple<int, int, int>> q;
        q.emplace_back(0, 0, 0);
        for (int step = 1; !q.empty(); ++step) {
            vector<tuple<int, int, int>> nxt;
            for (const auto &[X, Y, S] : q) {
                for (const auto &d : DIRS) {
                    int x = X + d[0], y = Y + d[1], s = S ^ d[2]; // tail
                    int x2 = x + s, y2 = y + (s ^ 1); // head
                    if (x2 < n && y2 < n && !st[x][y][s] && grid[x][y] == 0 && grid[x2][y2] == 0
                        && (d[2] == 0 || grid[x + 1][y + 1] == 0)) {
                            if (x == n - 1 && y == n - 2) return step;
                            st[x][y][s] = 1;
                            nxt.emplace_back(x, y, s);
                        }
                }
            }
            q = move(nxt);
        }
        return -1;
    }
};

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        int r = 0; // start from [0, r].
        sort(coins.begin(), coins.end());
        for (int coin : coins) {
            // to make [0, r] & [coin, coin + r] connected,
            // coin should not be greater than 'r + 1'.
            if (coin <= r + 1) r += coin;
            else break;
        }
        return r + 1;
    }
};

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int p = find(nums.begin(), nums.end(), k) - nums.begin(), ans = 0;
        for (int i = p, bal = 0; i < nums.size(); ++i) {
            bal += nums[i] == k ? 0 : nums[i] < k ? -1 : 1;
            ++cnt[bal];
        }
        for (int i = p, bal = 0; i >= 0; --i) {
            bal += nums[i] == k ? 0 : nums[i] < k ? 1 : -1;
            ans += cnt[bal] + cnt[bal + 1];
        }
        return ans;
    }
};

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        for (int left = 0, right = 0, product = 1; right < n; ++right) {
            product *= nums[right];
            while (left <= right && product >= k)
                product /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }
};

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        function<int(int)> count = [&](int lower) {
            int res = 0;
            for (int left = 0, right = 0, cnt = 0; right < n; ++right) {
                if (nums[right] & 1) ++cnt;
                while (cnt > lower)
                    if (nums[left++] & 1) --cnt;
                res += right - left + 1;
            }
            return res;
        };
        return count(k) - count(k - 1);
    }
};

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        function<int(int)> count = [&](int lower) {
            int freq[3] = {0}, res = 0;
            for (int left = 0, right = 0, cnt = 0; right < n; ++right) {
                if (++freq[s[right] - 'a'] == 1) ++cnt;
                while (cnt > lower)
                    if (--freq[s[left++] - 'a'] == 0) --cnt;
                res += right - left + 1;
            }
            return res;
        };
        return count(3) - count(2);
    }
};

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n);
        for (auto &b : bookings) {
            int first = b[0], last = b[1], seats = b[2];
            diff[first - 1] += seats;
            if (last < n) diff[last] -= seats;
        }
        for (int i = 1; i < n; ++i) diff[i] += diff[i - 1];
        return diff;
    }
};