Revise paste InMobi_OA_2

#include <bits/stdc++.h> // Includes all standard libraries (common in competitive programming)

using namespace std;

// Using long long for integer type for larger values
#define int long long

// Global timer for DFS start/end times
int dfs_timer;

// Max log for binary lifting (2^23 > 8*10^6, safe for n up to 10^6)
const int MAX_LOG = 24;

/**
 * @brief Performs DFS to calculate start/end times and immediate parents.
 * @param u Current node
 * @param p Parent node
 * @param st Start time array
 * @param en End time array
 * @param up Ancestor table (up[u][0] is parent of u)
 * @param adj Adjacency list
 */
void precompute_dfs(int u, int p, vector<int>& st, vector<int>& en,
                    vector<vector<int>>& up, const vector<vector<int>>& adj) {
    up[u][0] = p;
    st[u] = dfs_timer++;
    for (int v : adj[u]) {
        if (v != p) {
            precompute_dfs(v, u, st, en, up, adj);
        }
    }
    en[u] = dfs_timer;
}

/**
 * @brief Checks if node u is an ancestor of node v.
 */
bool is_ancestor(int u, int v, const vector<int>& st, const vector<int>& en) {
    return (st[u] <= st[v] && en[u] >= en[v]);
}

/**
 * @brief Finds the Lowest Common Ancestor (LCA) of nodes u and v.
 */
int find_lca(int u, int v, const vector<vector<int>>& up,
             const vector<int>& st, const vector<int>& en) {
    // First, check if one is an ancestor of the other
    if (is_ancestor(u, v, st, en)) return u;
    if (is_ancestor(v, u, st, en)) return v;

// Binary lifting to find LCA
    for (int i = MAX_LOG - 1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v, st, en)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}

signed main() {
    // Optimize C++ streams for speed
    ios::sync_with_stdio(false);
    cin.tie(NULL);

int n, m;
    cin >> n >> m;

vector<vector<int>> adj(n + 1);
    vector<vector<int>> up(n + 1, vector<int>(MAX_LOG, 0));
    vector<int> degree(n + 1, 0);
    vector<int> startTime(n + 1), endTime(n + 1);

// Read tree edges
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

// Run DFS and precomputation, rooting at 1
    // Node 0 is a virtual parent for the root
    dfs_timer = 0;
    precompute_dfs(1, 0, startTime, endTime, up, adj);
    endTime[0] = dfs_timer; // Set end time for virtual parent

// Fill the binary lifting (ancestor) table
    for (int i = 1; i < MAX_LOG; i++) {
        for (int j = 1; j <= n; j++) {
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }

// 'delta' array for difference array on tree
    vector<int> delta(n + 1, 0);

// Process m queries
    for (int j = 0; j < m; j++) {
        int u, v;
        cin >> u >> v;

int lca = find_lca(u, v, up, startTime, endTime);

// This is a standard difference array technique for path updates on a tree.
        // Add 1 to u, add 1 to v, subtract 1 from LCA, subtract 1 from parent of LCA.
        delta[u]++;
        delta[v]++;
        delta[lca]--;
        if (up[lca][0] != 0) { // Avoid decrementing virtual parent
            delta[up[lca][0]]--;
        }
    }

// Use a queue to process nodes from leaves up (topological sort)
    // This accumulates the delta values from children to parents
    queue<int> q;
    vector<int> processing_degree = degree; // Copy degrees for processing
    for (int i = 1; i <= n; i++) {
        if (processing_degree[i] == 1) {
            q.push(i);
        }
    }

// If n=1, root is also a leaf.
    if (n == 1) {
        q.push(1);
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();

int p = up[u][0];
        if (p == 0) continue; // Stop at the root's virtual parent

// Add child's sum to its parent
        delta[p] += delta[u];
        processing_degree[p]--;

// If parent is now a "leaf" (relative to its own parent), add to queue
        if (processing_degree[p] == 1 && p != 1) { // p != 1 ensures root isn't re-added
             q.push(p);
        }
    }

// After the BFS, delta[1] (the root) needs its final processing
    // if it wasn't a leaf.
    // The original logic handles the root correctly when its degree
    // becomes 1 (or 0 if it was the last node).
    // Let's re-verify the original logic.
    // The original loop is correct. When deg[p] == 1, it means all children
    // of p have been processed, and only the edge to *its* parent remains.
    // So we push p to be processed. This works for the root 1 as well,
    // as up[1][0] is 0, and the loop will just add delta[1] to delta[0]
    // and terminate.
    // My previous 'processing_degree' and check for p != 1 was an 
    // over-complication. Reverting to the simpler, correct original logic.
    
    // Re-doing the leaf-processing part to match the (correct) original
    queue<int> q_simple;
    for(int i = 1; i <= n; i++){
        // Node 1 is the root, it shouldn't be added as a leaf
        // unless n=1 or it's a leaf (n=2).
        if(degree[i] == 1 && i != 1) {
            q_simple.push(i);
        }
    }
    // Handle n=1 case
    if (n == 1) q_simple.push(1);
    // Handle n=2 case (root is a leaf)
    if (n == 2 && degree[1] == 1) q_simple.push(1);
    
    vector<int> final_ans = delta;

while(!q_simple.empty()){
        int u = q_simple.front();
        q_simple.pop();

int p = up[u][0];
        if (p == 0) continue; // Should not happen if root isn't pushed incorrectly

final_ans[p] += final_ans[u];
        degree[p]--;
        
        // If parent (and not root) now only has parent edge, push it.
        if(degree[p] == 1 && p != 1) {
            q_simple.push(p);
        }
    }

// The original code's logic was simpler and more robust.
    // It works because even the root (1) will be pushed when degree[1] == 1,
    // (after all its children are processed), and its update will
    // go to node 0, which is fine.

// --- Using the original, correct logic ---
    queue<int> q_original;
    for(int i = 1; i <= n; i++){
        if(degree[i] == 1) {
            q_original.push(i);
        }
    }
    
    // This loop correctly propagates sums up from all leaves.
    while(!q_original.empty()){
        int u = q_original.front();
        q_original.pop();
        
        int p = up[u][0];
        if (p == 0) continue; // Don't process parent of root

delta[p] += delta[u];
        degree[p]--;
        
        if(degree[p] == 1 && p != 0) { // p!=0 is technically redundant but safe
            q_original.push(p);
        }
    }
    // --- End original logic ---

// Print the final counts for each node
    for (int i = 1; i <= n; i++) {
        cout << delta[i] << ' ';
    }
    cout << '\n';

return 0;
}