自动搬运

查看原文

来自洛谷，原作者为

	icaijy **

搬运于2025-08-24 23:08:26，当前版本为作者最后更新于2025-01-12 10:09:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这一道题的 subtask 给了很多线索。先跳过用来打暴力的第一个子任务，我们从第二个子任务开始观察。

第二个子任务有 $u_i=i, v_i=i+1$，显然意思是整个树是一个链。我们可以把这题从树转换到数组来做。相当于给你一个只包含 $0$ 和 $1$ 的数组，求你对相同长度，全为 $0$ 的数组进行至少几次区间翻转操作能将其变成第一个数组。

考虑如下例子：

1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1

发现一段连续的相同的段，我们肯定会一起操作。因此我们可以把它简化成：

1 0 1 0 1 0 1

这时我们有两种选择，第一种是直接每次操作 $1$ 的位置把 $0$ 变成 $1$，这样要操作四次。或者先把整个数组翻转，再操作 $0$ 的位置，不过这样仍然是四次。因此这一子任务只需要输出有几个连续的 $1$ 即可。

接下来考虑第三个子任务，发现这个和我们刚刚考虑的情况很相似，即把联通的一大块看成一个点。但这时会发现我们刚刚只操作 $1$ 或都翻转后操作 $0$ 的办法行不通了。这时我们画一个新的例子：

若沿用之前的思路，那这个图需要四次操作。不过我们发现这个图可以这样操作：

1. 翻转整个图。
2. 断开下面三个 $1$ 的边，再翻转整个图。
3. 翻转根节点，即顶部的 $1$。

我们发现，对于树只需要操作它的层数次即可。

不过层数该怎么求呢？首先发现假如 $0$ 在叶节点，或它的子孙也都是 $0$，那就可以不管了，直接断开连接让他们一直不改即可。我们真正要改的是 $1$。这时，我们只需构造一个树使得他的层数最小即可。这里的层数是指根节点到叶节点 $0,1$ 交替的次数。比如上图根节点到叶节点最远是 $1,0,1$，所以层数是 $3$，答案也是 $3$。

这时只需最小化最长的链。这时可以用树的直径的思路。找出从 $1$ 开始且以 $1$ 结束最长的链，让他们的中点作为根节点，这样就保证了层数最小，这题也就做出来了。这里我用两次 dfs 找直径，不会的话先去做一下树的直径。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[1000005]={114514};
vector<int> adj[1000005];

int maxp,maxd;

void dfs(int cur,int par,int deep){
    if (a[cur]!=a[par]) deep++;
    if (a[cur]==1&&deep>maxd) {
        maxd=deep;
        maxp=cur;
    }
    for (int i:adj[cur]) if (i!=par) dfs(i,cur,deep);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n;
    bool noone=true; // 特判一波全为0
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        if (a[i]==1) noone=false;
    }
    if (noone){
        cout<<0;
        return 0;
    }
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0,0);
    maxd=0;
    dfs(maxp,0,0);
    cout<<(maxd+1)/2;
    return 0;
}