2fe949ca1637ba9d057272a1b1623a15ecc9dc3460b1983764299c7fc50fbbb0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 = enable_if_t<is_integral_v<T> && 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 = enable_if_t<is_integral_v<T> && is_unsigned_v<T>>, typename = void>
constexpr Int128(T val) : high(0), low(static_cast<uint64_t>(val)) {}
explicit Int128(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 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 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 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;
}
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;
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('-');
reverse(res.begin(), res.end());
return res;
}
friend ostream& operator<<(ostream& os, const Int128& val) { return os << val.to_string(); }
};
typedef pair<int, int> pii;
constexpr int N = 1e6 + 10;
constexpr ll inf = 1e18;
constexpr unsigned long long M = 998244353;
int n, a[N], b[N], p, q, siz[N], head[N], tot, f[N];
ll atot, btot, dp[N], cf[N], expt[N];
Int128 ans, mi;
bool vis[N];
struct p {
int to, nxt;
} edge[N << 1];
void add(int x, int y) {
edge[++tot].nxt = head[x];
edge[tot].to = y;
head[x] = tot;
}
stack<int> st1, st2;
queue<int> que;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
atot += a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
btot += b[i];
}
if (atot != btot) {
cout << "NIE" << '\n';
return 0;
}
for (int i = 1; i < n; i++) {
cin >> p >> q;
add(p, q);
add(q, p);
}
st1.push(1);
while (!st1.empty()) {
int u = st1.top();
st1.pop();
st2.push(u);
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == f[u]) continue;
f[v] = u;
st1.push(v);
}
}
while (!st2.empty()) {
int id = st2.top();
st2.pop();
siz[id] = 1;
ll totcnt = 0;
for (int i = head[id]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == f[id]) continue;
if (!vis[id]) {
dp[id] = expt[to];
totcnt += dp[to];
vis[id] = 1;
} else {
cf[to] = dp[id] - expt[to];
totcnt += dp[to] + cf[to];
}
siz[id]++;
}
expt[id] = b[id] - a[id] + siz[id] * dp[id] - totcnt;
}
que.push(1);
while (!que.empty()) {
int x = que.front();
que.pop();
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == f[x]) continue;
cf[to] += cf[x];
que.push(to);
}
Int128 cur = dp[x] + cf[x];
ans += cur;
mi = (mi < cur) ? mi : cur;
}
cout << "TAK" << '\n';
ans -= mi * n;
cout << ans << '\n';
return 0;
}