题解：P11562 【MX-X7-T3】[LSOT-3] 寄存器

· · 题解

这一道题的 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;
}