OI XXV - prz (Short)

// https://szkopul.edu.pl/problemset/problem/o4N9I1hFMnpCUm0sjmIEYx_2/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

struct Int128 {
    uint64_t high{0};
    uint64_t low{0};

    constexpr Int128() = default;
    constexpr Int128(uint64_t val) : high(0), low(val) {}

    constexpr Int128& operator+=(uint64_t val) {
        low += val;
        if (low < val) high++;
        return *this;
    }

    constexpr Int128& operator+=(const Int128& b) {
        low += b.low;
        high += b.high + (low < b.low ? 1 : 0);
        return *this;
    }

    std::string to_string() const {
        if (high == 0 && low == 0) return "0";
        uint64_t h = high, l = low;
        std::string res;
        while (h > 0 || l > 0) {
            uint64_t rem = h % 10;
            h /= 10;
            uint64_t cur = (rem << 32) | (l >> 32);
            uint64_t q_mid = cur / 10;
            rem = cur % 10;
            cur = (rem << 32) | (l & 0xFFFFFFFFULL);
            uint64_t q_low = cur / 10;
            rem = cur % 10;
            l = (q_mid << 32) | q_low;

            res.push_back(static_cast<char>('0' + rem));
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const Int128& val) { return os << val.to_string(); }
};

int x[sizik], y[sizik], y_prime[sizik];
Int128 ans(0);

std::vector<int> kra[sizik];

int64_t dp[sizik];
int64_t z[sizik];

void dfs(int v, int p) {
    dp[v] = y_prime[v];
    for (const auto& u : kra[v]) {
        if (u == p) continue;
        dfs(u, v);
        dp[v] += dp[u];
    }
}

void dfs1(int v, int p) {
    for (const auto& u : kra[v]) {
        if (u == p) continue;
        z[u] = z[v] - dp[u];
        dfs1(u, v);
    }
}

void solve() {
    int n;
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        std::cin >> x[i];
    }

    for (int i = 1; i <= n; i++) {
        std::cin >> y[i];
    }

    int64_t s = 0;
    for (int i = 1; i <= n; i++) {
        y_prime[i] = y[i] - x[i];
        s += (int64_t)y_prime[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        std::cin >> a >> b;

        kra[a].push_back(b);
        kra[b].push_back(a);
    }

    if (s != 0) {
        std::cout << "NIE\n";
        return;
    }

    dfs(1, 1);
    dfs1(1, 1);

    int64_t z_min = 0;
    for (int i = 1; i <= n; i++) {
        z_min = std::min(z_min, z[i]);
    }

    for (int i = 1; i <= n; i++) {
        ans += static_cast<uint64_t>(z[i] - z_min);
    }

    std::cout << "TAK\n";
    std::cout << ans << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}