Balanced Tree node.js

gistfile1.txt

// Template Starts here Fast IO!
'use strict';

var input = require('fs').readFileSync(0).toString().trim().split('\n');
var pos = 0;
var getLine = () => input[pos++];

function solve() {
        const n = +getLine();
        const l = new Array(n);
        const r = new Array(n);
        
        // Read L and R values
        for (let i = 0; i < n; i++) {
                const [li, ri] = getLine().split(' ');
                l[i] = +li;
                r[i] = +ri;
        }
        
        if (n === 1) return l[0];
        
        // Use Uint32Array for better performance with numbers
        const deg = new Uint32Array(n);
        const mix = new Uint32Array(n);
        
        // Process edges
        for (let i = 0; i < n - 1; i++) {
                const [u, v] = getLine().split(' ');
                const ui = +u - 1;
                const vi = +v - 1;
                deg[ui]++;
                deg[vi]++;
                mix[ui] ^= vi;
                mix[vi] ^= ui;
        }
        
        // Pre-allocate array capacity for leaves
        const h = [];
        let hSize = 0;
        for (let i = 0; i < n; i++) {
                if (deg[i] === 1) {
                        h[hSize++] = i;
                }
        }
        
        let ans = 0;
        let hPos = 0;
        
        // Process nodes
        for (let i = 0; i < n - 1; i++) {
                const u = h[hPos++];
                const v = mix[u];
                
                if (l[u] > r[v]) {
                        ans += l[u] - r[v];
                        l[v] = r[v];
                } else if (l[u] > l[v]) {
                        l[v] = l[u];
                }
                
                mix[v] ^= u;
                deg[v]--;
                if (deg[v] === 1) {
                        h[hSize++] = v;
                }
        }
        
        return ans + l[h[hPos]];
}

// Process all test cases
const t = +getLine();
let ans = '';
for (let i = 0; i < t; i++) {
        ans += solve() + '\n';
}
process.stdout.write(ans);