题解：CF2035F Tree Operations

梨花诗 · 2026-04-25 21:58:08 · 题解

很好的题。

首先你发现是不可能无解的，为什么呢？

我们可以用若干次操作将树的所有点权变成 0 或 1，这个是很简单的。然后可以用 2n 次操作将一个点和根同时取反。

具体来说假设我们想将点 u 和根一起取反，我们先用根将 u 取反，其他所有都自己取反自己，最终得到只有根和 u 没变，其他人都取反了，所以再做一次即可。

最终只有根可能是 1 其他都是 0，我们可以将这个锅甩给一号节点，这样它直接开始取反然后结束即可。

那么既然一定有解，我们可以看看能不能二分，但是这东西真的有单调性吗？感觉肯定是没有的，那么就倒闭了吗？我们再思考下假设 res 是可行的，那么是不是 res + 2n 显然也是可行的。所以我们在枚举模 2n 的余数下是有单调性滴。

接下来看看怎么判断 m 次操作是否可以完成吧，首先给每个点分配一个得到的操作数 f_i，按照题意分配就行，然后对于每个点我们计算将其子树都变成 0，最少还需要几次额外的操作。转移都很简单注意下奇偶性就行。

复杂度 O(n^2\log V)，简单估算下 V 大概是 2 \times 10^{12} 加一些微调的。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
typedef long long ll;
using namespace std;
const int N = 2000 + 10;
int a[N]; vector<int> v[N]; int n, x;
ll f[N];
ll dfs(int u, int fa)
{
    ll nd = a[u];
    for(int s : v[u])
    {
        if(s == fa) continue;
        nd += dfs(s, u);
    }
    nd -= f[u];
    if(nd >= 0) return nd;
    else {nd = -nd; return nd&1?1:0;}
}
bool check(ll m)
{
    ll r = m % n;
    rep(i, 1, n) f[i] = m / n; rep(i, 1, r) f[i] ++;
    return dfs(x, -1) == 0;
}
int main()
{
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T -- )
    {
        cin >> n >> x;
        rep(i, 1, n) cin >> a[i], v[i].clear();
        rep(i, 1, n - 1)
        {
            int x, y; cin >> x >> y; v[x].push_back(y);
            v[y].push_back(x);
        }
        ll ans = 1e18;
        rep(rem, 0, n*2 - 1)
        {
            ll l = 0, r = 2e9, best = -1;
            while(l <= r)
            {
                ll mid = l + r >> 1;
                if(check(mid*2*n+rem)) r = mid - 1, best = mid;
                else l = mid + 1;
            }
            if(best != -1) ans = min(ans, best * 2 * n + rem);
        }
        cout << ans << '\n';
    }
    return 0;
}