题目大意

有 $n$ 个人，第 $i$ 个人的初始余额为 $x_i$，目标余额为 $y_i$。他们构成一个树形好友网络（$n-1$ 条边，连通）。每人可以执行操作：同时向所有好友转账 1 拜托币（自己减少度数，每个好友增加 1）。求是否能用这种操作达到目标状态，如果能，求最少操作次数。

问题分析

操作的性质

设第 $i$ 个人执行了 $a_i$ 次操作（向外转账），那么：

• 对于第 $i$ 个人：最终余额 = $x_i - d_i \cdot a_i + \sum_{j \in N(i)} a_j$
• 其中 $d_i$ 是 $i$ 的度数，$N(i)$ 是 $i$ 的邻居集合

我们要找到非负整数 $a_1, \dots, a_n$ 使得对于所有 $i$：

线性方程组形式

整理得：

设 $b_i = y_i - x_i$，则方程是：

写成矩阵形式：$L \vec{a} = \vec{b}$，其中 $L$ 是图的拉普拉斯矩阵：

• 对角线 $L_{ii} = -d_i$
• 非对角线 $L_{ij} = 1$ 如果 $i,j$ 相邻，否则 $0$

拉普拉斯矩阵的性质

对于连通图：

1. 拉普拉斯矩阵的秩是 $n-1$
2. 零空间由全 1 向量张成：$L \cdot (1,1,\dots,1)^T = 0$
3. 方程有解当且仅当 $\sum b_i = 0$（资金守恒）

求解策略

1. 可行性检查：如果 $\sum (y_i - x_i) \neq 0$，输出 NIE
2. 特解构造：以节点 1 为根，DFS 求解
   • 对于叶子节点 $u$，方程是：$a_{\text{parent}} - a_u = b_u$（度数为 1）
   • 可以自底向上确定 $a_i$ 的相对值
3. 最小化总操作次数：由于解空间是一维的（$a_i + c$ 也是解），我们要找到常数 $c$ 使得 $\sum a_i$ 最小且所有 $a_i \geq 0$

算法实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e6 + 5;

vector<int> adj[MAXN];
ll x[MAXN], y[MAXN], diff[MAXN];
ll a[MAXN];  // 每个节点的操作次数
int parent[MAXN], deg[MAXN];
int n;

void dfs(int u, int p) {
    parent[u] = p;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

bool solve() {
    // 检查资金守恒
    ll sum_x = 0, sum_y = 0;
    for (int i = 1; i <= n; i++) {
        sum_x += x[i];
        sum_y += y[i];
    }
    if (sum_x != sum_y) return false;
    
    // 计算差值
    for (int i = 1; i <= n; i++) {
        diff[i] = y[i] - x[i];
    }
    
    // 以1为根DFS建立父子关系
    dfs(1, -1);
    
    // 自底向上计算相对操作次数
    vector<int> order;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1 && i != 1) {  // 叶子节点（除了根）
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            // 对于树来说，除了父节点其他都是子节点，这里应该只处理父节点
        }
        
        if (parent[u] != -1) {
            bool all_children_processed = true;
            for (int v : adj[parent[u]]) {
                if (v != parent[parent[u]] && find(order.begin(), order.end(), v) == order.end()) {
                    all_children_processed = false;
                    break;
                }
            }
            if (all_children_processed && find(order.begin(), order.end(), parent[u]) == order.end()) {
                q.push(parent[u]);
            }
        }
    }
    reverse(order.begin(), order.end());
    
    // 计算相对操作次数
    for (int u : order) {
        if (u == 1) continue;  // 根节点最后处理
        
        int p = parent[u];
        // 方程: a[p] - a[u] = diff[u] - (已经确定的子节点贡献)
        // 简化: 对于树，每个非根节点有: a[p] - a[u] = diff[u]
        a[u] = a[p] - diff[u];
    }
    
    // 处理根节点
    // 根节点的方程: sum_{v in children} a[v] - deg[1] * a[1] = diff[1]
    ll children_sum = 0;
    for (int v : adj[1]) {
        children_sum += a[v];
    }
    a[1] = (children_sum - diff[1]) / deg[1];
    
    // 验证并调整非负性
    ll min_a = *min_element(a + 1, a + n + 1);
    if (min_a < 0) {
        ll shift = -min_a;
        for (int i = 1; i <= n; i++) {
            a[i] += shift;
        }
    }
    
    // 验证解
    for (int i = 1; i <= n; i++) {
        ll actual = x[i] - deg[i] * a[i];
        for (int j : adj[i]) {
            actual += a[j];
        }
        if (actual != y[i]) return false;
    }
    
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> y[i];
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    
    if (solve()) {
        cout << "TAK\n";
        ll total_ops = 0;
        for (int i = 1; i <= n; i++) {
            total_ops += a[i];
        }
        cout << total_ops << "\n";
    } else {
        cout << "NIE\n";
    }
    
    return 0;
}

关键点说明

1. 可行性条件

因为每次操作只是资金在系统内重新分配，总资金不变。

2. 解的结构

解空间是 $a_i + c$（$c$ 是任意常数），因为：

• 如果 $a_i$ 是解，那么 $a_i + c$ 也是解
• $L \cdot (c,c,\dots,c)^T = 0$

3. 最小化总操作次数

找到最小的 $c$ 使得所有 $a_i + c \geq 0$，即 $c = -\min(a_i)$。

复杂度分析

• 时间复杂度：$O(n)$，线性 DFS
• 空间复杂度：$O(n)$

总结

本题的关键是将转账操作建模为图上的线性方程组，利用树的特性和拉普拉斯矩阵的性质高效求解。算法核心是资金守恒检查和自底向上的相对值计算。

算法标签：树结构、线性代数、图论、DFS、贪心