c30eed56f155a7bb3c983d115689820823c9d09396108f633409bef26c714208
// 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 {
int64_t high{0};
uint64_t low{0};
constexpr Int128() = default;
constexpr Int128(int64_t h, uint64_t l) : high(h), low(l) {}
template<typename T, typename = std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>>>
constexpr Int128(T val) : high(val < 0 ? -1 : 0), low(static_cast<uint64_t>(static_cast<int64_t>(val))) {}
template<typename T, typename = std::enable_if_t<std::is_integral_v<T> && std::is_unsigned_v<T>>, typename = void>
constexpr Int128(T val) : high(0), low(static_cast<uint64_t>(val)) {}
explicit Int128(std::string_view s) {
*this = 0;
if (s.empty()) return;
bool neg = false;
size_t idx = 0;
if (s[0] == '-') {
neg = true;
idx = 1;
} else if (s[0] == '+') {
idx = 1;
}
for (; idx < s.size(); ++idx) {
if (s[idx] < '0' || s[idx] > '9') {
throw std::invalid_argument("Invalid character in numeric string");
}
*this = (*this * 10) + (s[idx] - '0');
}
if (neg) *this = -(*this);
}
constexpr Int128 operator+() const { return *this; }
constexpr Int128 operator~() const { return Int128(~high, ~low); }
constexpr Int128 operator-() const {
uint64_t new_low = ~low + 1;
int64_t new_high = ~high + (new_low == 0 ? 1 : 0);
return Int128(new_high, new_low);
}
constexpr bool operator!() const { return high == 0 && low == 0; }
constexpr explicit operator bool() const { return high != 0 || low != 0; }
constexpr Int128 operator+(const Int128& b) const {
uint64_t res_low = low + b.low;
int64_t carry = (res_low < low) ? 1 : 0;
int64_t res_high = high + b.high + carry;
return Int128(res_high, res_low);
}
constexpr Int128 operator-(const Int128& b) const {
uint64_t res_low = low - b.low;
int64_t borrow = (low < b.low) ? 1 : 0;
int64_t res_high = high - b.high - borrow;
return Int128(res_high, res_low);
}
constexpr Int128 operator*(const Int128& b) const {
uint64_t a0 = low & 0xFFFFFFFFULL, a1 = low >> 32;
uint64_t b0 = b.low & 0xFFFFFFFFULL, b1 = b.low >> 32;
uint64_t p00 = a0 * b0;
uint64_t p01 = a0 * b1;
uint64_t p10 = a1 * b0;
uint64_t p11 = a1 * b1;
uint64_t mid1 = p01 + (p00 >> 32);
uint64_t mid2 = p10 + (mid1 & 0xFFFFFFFFULL);
uint64_t res_low = (p00 & 0xFFFFFFFFULL) | (mid2 << 32);
uint64_t res_high_from_low = p11 + (mid1 >> 32) + (mid2 >> 32);
int64_t res_high = static_cast<int64_t>(res_high_from_low) + static_cast<int64_t>(low * static_cast<uint64_t>(b.high)) +
static_cast<int64_t>(static_cast<uint64_t>(high) * b.low);
return Int128(res_high, res_low);
}
constexpr Int128 operator&(const Int128& b) const { return Int128(high & b.high, low & b.low); }
constexpr Int128 operator|(const Int128& b) const { return Int128(high | b.high, low | b.low); }
constexpr Int128 operator^(const Int128& b) const { return Int128(high ^ b.high, low ^ b.low); }
constexpr Int128 operator<<(int shift) const {
if (shift <= 0) return *this;
if (shift >= 128) return Int128(0, 0);
if (shift >= 64) {
return Int128(static_cast<int64_t>(low << (shift - 64)), 0);
}
return Int128((high << shift) | static_cast<int64_t>(low >> (64 - shift)), low << shift);
}
constexpr Int128 operator>>(int shift) const {
if (shift <= 0) return *this;
if (shift >= 128) {
int64_t sign_ext = high >> 63;
return Int128(sign_ext, static_cast<uint64_t>(sign_ext));
}
if (shift >= 64) {
int64_t sign_ext = high >> 63;
return Int128(sign_ext, static_cast<uint64_t>(high >> (shift - 64)));
}
return Int128(high >> shift, (low >> shift) | (static_cast<uint64_t>(high) << (64 - shift)));
}
constexpr bool operator==(const Int128& b) const { return high == b.high && low == b.low; }
constexpr bool operator!=(const Int128& b) const { return !(*this == b); }
constexpr bool operator<(const Int128& b) const {
if (high != b.high) return high < b.high;
return low < b.low;
}
constexpr bool operator<=(const Int128& b) const { return !(b < *this); }
constexpr bool operator>(const Int128& b) const { return b < *this; }
constexpr bool operator>=(const Int128& b) const { return !(*this < b); }
private:
static constexpr void udivmod(uint64_t num_h, uint64_t num_l, uint64_t den_h, uint64_t den_l, uint64_t& q_h, uint64_t& q_l, uint64_t& r_h,
uint64_t& r_l) {
q_h = q_l = r_h = r_l = 0;
for (int i = 127; i >= 0; --i) {
r_h = (r_h << 1) | (r_l >> 63);
r_l = r_l << 1;
uint64_t bit = (i >= 64) ? ((num_h >> (i - 64)) & 1ULL) : ((num_l >> i) & 1ULL);
r_l |= bit;
bool ge = (r_h > den_h) || (r_h == den_h && r_l >= den_l);
if (ge) {
uint64_t borrow = (r_l < den_l) ? 1ULL : 0ULL;
r_l -= den_l;
r_h = r_h - den_h - borrow;
if (i >= 64)
q_h |= (1ULL << (i - 64));
else
q_l |= (1ULL << i);
}
}
}
public:
Int128 operator/(const Int128& b) const {
if (b == 0) throw std::domain_error("Division by zero in Int128");
bool neg = (high < 0) ^ (b.high < 0);
Int128 abs_a = (high < 0) ? -(*this) : *this;
Int128 abs_b = (b.high < 0) ? -b : b;
uint64_t q_h, q_l, r_h, r_l;
udivmod(abs_a.high, abs_a.low, abs_b.high, abs_b.low, q_h, q_l, r_h, r_l);
Int128 quotient(static_cast<int64_t>(q_h), q_l);
return neg ? -quotient : quotient;
}
Int128 operator%(const Int128& b) const {
if (b == 0) throw std::domain_error("Modulo by zero in Int128");
bool neg = (high < 0);
Int128 abs_a = (high < 0) ? -(*this) : *this;
Int128 abs_b = (b.high < 0) ? -b : b;
uint64_t q_h, q_l, r_h, r_l;
udivmod(abs_a.high, abs_a.low, abs_b.high, abs_b.low, q_h, q_l, r_h, r_l);
Int128 remainder(static_cast<int64_t>(r_h), r_l);
return neg ? -remainder : remainder;
}
Int128& operator+=(const Int128& b) { return *this = *this + b; }
Int128& operator-=(const Int128& b) { return *this = *this - b; }
Int128& operator*=(const Int128& b) { return *this = *this * b; }
Int128& operator/=(const Int128& b) { return *this = *this / b; }
Int128& operator%=(const Int128& b) { return *this = *this % b; }
Int128& operator&=(const Int128& b) { return *this = *this & b; }
Int128& operator|=(const Int128& b) { return *this = *this | b; }
Int128& operator^=(const Int128& b) { return *this = *this ^ b; }
Int128& operator<<=(int shift) { return *this = *this << shift; }
Int128& operator>>=(int shift) { return *this = *this >> shift; }
Int128& operator++() {
*this += 1;
return *this;
}
Int128 operator++(int) {
Int128 tmp = *this;
*this += 1;
return tmp;
}
Int128& operator--() {
*this -= 1;
return *this;
}
Int128 operator--(int) {
Int128 tmp = *this;
*this -= 1;
return tmp;
}
std::string to_string() const {
if (*this == 0) return "0";
bool neg = (high < 0);
uint64_t cur_h = static_cast<uint64_t>(neg ? (-*this).high : high);
uint64_t cur_l = neg ? (-*this).low : low;
std::string res;
while (cur_h != 0 || cur_l != 0) {
uint64_t q_h, q_l, r_h, r_l;
udivmod(cur_h, cur_l, 0, 10, q_h, q_l, r_h, r_l);
res.push_back(static_cast<char>('0' + r_l));
cur_h = q_h;
cur_l = q_l;
}
if (neg) res.push_back('-');
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]);
}
ans = n;
ans *= -z_min;
for (int i = 1; i <= n; i++) {
ans += z[i];
}
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;
}