题解：CF2035F Tree Operations

· · 题解

Statement

给定一棵以 x 为根的 n 个结点的树，结点 i 的初始值为 a_i。

若第 i 次操作的目标是 u，则你需要在 u 的子树中选择一个节点 v，并令 v 的权值增加或减少 1。你需要操作 m 次，i \leq n 时第 i 次操作的目标是结点 i，否则第 i 次操作的目标与第 i - n 次相同。

求出 m 的最小值，使得存在一种操作方案把所有结点的值都变为 0 或报告无解。

数据范围：数据组数 T \leq 100，n \leq 2 \times 10^3，\sum n \leq 2 \times 10^3，0 \leq a_i \leq 10^9。

Solution

首先，如果存在 m 次操作的方案，那么一定存在 m + 2n 次操作的方案（这是因为可以再进行 2n 次操作，每个结点先增加 1 再减少 1）。于是当操作次数除以 2n 得到的余数固定时，一个操作次数是否可行是具有单调性的，可以使用二分解决。

问题变为如何判定一个操作次数 m 是否可行。首先可以对每个结点计算出以其作为目标操作了几次，记为 g(i)。考虑树形 dp，设 f(i) 表示以结点 i 为根的子树中，还需要多少次操作才可以全部变为 0。计算 f 只需要初始令 f(i) = a_i，设 i 的父亲为 u，那么当 f(i) > g(i)，会对 f(u) 产生 f(i) - g(i) 的贡献，否则子树内有 g(i) - f(i) 次操作多余，每两次可以使用两次反转操作消除，但是当其为奇数时，需要向 f(u) 贡献 1 次操作。

这样我们可以在 \Theta(n) 的时间复杂度内判断，总时间复杂度为 O(n^2 \log V)，其中 V 表示操作次数上限。

给出结论：一定存在一种有限次操作方案完成题目的要求。注意可以使用 n 次操作让所有结点值在 0, 1 之间切换，下面直接构造方案：

故不存在无解的情况。

Solution (English)

First, if there exists a plan with m operations, then there must exist a plan with m + 2n operations (this is because we can perform an additional 2n operations, where each node is first incremented by 1 and then decremented by 1). Thus, when the remainder of the number of operations divided by 2n is fixed, the feasibility of a given number of operations exhibits monotonicity, allowing for a binary search approach.

The problem then becomes how to determine if a number of operations m is feasible. First, we can calculate how many times each node has been targeted as a goal, denoted as g(i). Consider a tree dynamic programming approach, where f(i) represents how many more operations are needed to make all nodes in the subtree rooted at node i equal to 0. To calculate f, we can initialize with f(i) = a_i. Let i's parent be u. If f(i) > g(i), it contributes f(i) - g(i) to f(u); otherwise, there are g(i) - f(i) excess operations in the subtree. Every two excess operations can be eliminated by using two flip operations, but if the excess is odd, we need to contribute 1 operation to f(u).

This allows us to determine feasibility in \Theta(n) time complexity, resulting in a total time complexity of O(n^2 \log V), where V represents the upper limit on the number of operations.

In conclusion, there definitely exists a finite sequence of operations to meet the problem's requirements. Note that we can use n operations to toggle all node values between 0 and 1. Here is the construction of the solution:

Thus, there are no cases with no solution.

Code

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

int n,root,a[2001];
vector<int> E[2001];
long long f[2001],g[2001];

int dfn[2001],rnk[2001],fa[2001],cntdfn;
void init(int u,int father){
    fa[u]=father,dfn[u]=++cntdfn,rnk[cntdfn]=u;
    for(int v :E[u])if(v!=father)init(v,u);
}
inline bool check(long long val){
    for(int i=1;i<=n;i++)f[i]=val/n+(i<=val%n),g[i]=a[i];
    f[0]=g[0]=0;
    for(int i=n;i>=1;i--){
        int u=rnk[i];
        g[fa[u]]+=f[u]<g[u]?g[u]-f[u]:((f[u]-g[u])&1);
    }
    return g[0]==0;
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&root);
        for(int i=1;i<=n;i++)E[i].clear();
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            E[u].push_back(v);
            E[v].push_back(u);
        }
        cntdfn=0;
        init(root,0);
        long long answer=1e18;
        for(int i=0;i<n*2;i++){
            int l=0,r=1e9;
            while(l<r){
                int mid=(l+r)>>1;
                if(check(1ll*mid*n*2+i))r=mid;
                else l=mid+1;
            }
            answer=min(answer,1ll*l*n*2+i);
        }
        printf("%lld\n",answer);
    }
    return 0;
}