题解 P8503 No mind to think

· · 题解

传送门

前置知识：

基环树。

题意：

分析：

Subtask 0：

考虑 dfs 来枚举每一种方案。开一个数组来表示每一条边是有向边还是无向边，在移动前先判断一条边是否能走。

实际能过 n\le6。

Subtask 1：

考虑优化暴力的 dfs。将边的状态进行状态压缩：用一个 n 位二进制数表示边的状态，第 i 位为 0 表示第 i 条边为有向边，为 1 表示第 i 条边为无向边。设 dp_{step,x,s} 表示已经完成了 f_{step}，当前位于 x 号点，边的状态为 s 的最小步数。枚举下一步的移动来进行转移。在移动前判断是否能走，移动后更新 s 和 step。由于每次移动距离增加 1，可以写成 bfs。

时间复杂度 \mathcal O(n^22^n)。

Subtask 2：

由于 1 号点能到达任何点，所以图弱联通。若边是无向边，则图是一棵基环树。

对较大的样例使用瞪眼法可得，有很多边的状态是不需要存储的，可以直接把它们当做双向边考虑。观察哪些边不需要存储。

对于外向树的情况，即只有 n-1 条有向边、1 号点作为树根时，若到达了 i 号点，则意味着从到根节点到 i 的路径上所有边都已走过，所以可以从 i 到达任意祖先，因此从 i 到 i+1 一定可以沿着树上的最短路走，与所有边均为无向边的情况是一样的，所以不需要存储任何边的状态。

考虑拓展到基环树上。对于环上挂着的树，其实与单独的外向树并无不同，不需要存储边的状态。所以只需考虑环上的边的状态。

因为 1 号点可以到达所有点，所以一般来说，一个环由两条方向相反的链组成，如样例一：

称两链的终点相交的位置为“关键点”。在样例一中，关键点即为 6 号点。

与外向树一样，我们考虑将所有的边替换为无向边的情况。发现有向与无向的区别在于能否“跨过”关键点：对于一种无向图上的方案，若不跨过关键点，则必定可以在有向图上完成。

可以证明，可以跨过关键点的充要条件是指向关键点的两条边都被经过。所以只用存这两条边的状态即可。我们称这两条边为“关键边”。

特殊情况下，一个环不由两条方向相反的链组成，而是所有边方向相同，则认为 1 号点所在的树的根是关键点；只有一条关键边，则认为另一条关键边已经被经过。与一般情况处理方法相同。

时间复杂度 \mathcal O(n^2)。

Subtask 3：

由于起点 i 与终点 i+1 已定，我们考虑直接求出最优的路径。对于树，最优路径长度就是两点的深度之和减两倍的最近公共祖先的深度；对于环，由于只与是否经过两条关键边相关，所以转移最多有四种情况：不经过关键边、经过某一条关键边、经过两条关键边。

若经过了一条关键边并且经过了起点与终点的其中一个点两次，则可以看做先进行了一次不经过关键边的转移，再进行一次从一个点到关键边再回来的转移。后者与另一个点无关，可以在转移前或后考虑。

若经过了一条关键边但起点与终点均只经过一次，那么一定经过了关键点，即要么起点与终点之一是关键点，要么跨过了关键点，此时两条关键边均被经过。

所以特判起点和终点是关键点的情况，否则就只有两种情况：不经过关键边和经过两条关键边，即不经过关键点和经过关键点。分类讨论即可。具体写法可以参考代码。

复杂度 \mathcal O(n\log n)。瓶颈在求 LCA，所以理论可以做到 \mathcal O(n)。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;
bool Mbe;
inline int read() {
    int res=0; char ch;
    do ch=getchar(); while(!isdigit(ch));
    do res=res*10+(ch^48); while(isdigit(ch=getchar()));
    return res;
}
template <typename T>
inline void to_min(T &x, const T y) {
    if(x>y) x=y;
}
template <typename T>
inline T min_(const T x, const T y) {
    return x<y? x: y;
}
const int mN=5e5+9, mD=20;
int n;
int oe=1, head[mN], e[mN*2][2];
inline void add(const int x, const int y) {
    e[++oe][0]=head[x], e[head[x]=oe][1]=y;
}

bool vis[mN];
int m, r[mN], key_r, a[mN];
/*
r, a 均用来存环上节点编号
key_r 为关键点
如果 key_r=0 则关键点为 1 号点对应的根节点，且边方向为 r[1]->r[m]
否则边方向为 r[1]->r[key_r]<-r[m]
*/
bool dfs_r(int x, int f) {  //找环
    bool res=0;
    vis[x]=1;
    for(int t=head[x], y; y=e[t][1], t; t=e[t][0]) if(y && y!=f) {
        if(vis[y] || dfs_r(y, x)) {
            e[t][1]=e[t^1][1]=0, res=1;
            r[++m]=y;
            if(!key_r && !(t&1)) key_r=m;
        }
    }
    return res && x!=r[1];
}
int d[mN], fa[mN][mD], col[mN];
void dfs_pre(int x, int c) {    //染色并预处理 LCA 数组
    col[x]=c;
    for(int t=1; fa[x][t-1]; ++t) fa[x][t]=fa[fa[x][t-1]][t-1];
    for(int t=head[x], y; y=e[t][1], t; t=e[t][0]) if(y && y!=fa[x][0]) {
        fa[y][0]=x, d[y]=d[x]+1, dfs_pre(y, c);
    }
}
int cal_lca(int x, int y) {
    if(d[x]<d[y]) swap(x, y);
    for(int t=mD-2; ~t; --t) if(d[fa[x][t]]>=d[y]) x=fa[x][t];
    if(x==y) return x;
    for(int t=mD-2; ~t; --t) if(fa[x][t]^fa[y][t]) x=fa[x][t], y=fa[y][t];
    return fa[x][0];
}

ll dp[mN][2][2];
//第一维表示阶段，第二、三维表示是否经过左、右侧的关键边。

bool Men;
int main() {
    cerr<<"memory: "<<(&Mbe-&Men>>20)<<" MB\n";

    n=read();
    rep(__, 1, n) {
        int x=read(), y=read();
        add(x, y), add(y, x);
    }
    dfs_r(1, 0);

    if(key_r) {
        //使得关键点位于 m，这样不经过关键点的路径一定在 [1,m) 内。
        a[0]=r[key_r];
        rep(i, 1, m-key_r) a[i]=r[i+key_r];
        rep(i, m-key_r+1, m) a[i]=r[i-(m-key_r)];
    } else {
        a[0]=a[m]=r[1];
        rep(i, 1, m-1) a[i]=r[i+1];
    }
    d[0]=-1;
    if(!key_r) {
        rep(i, 0, m-1) dfs_pre(a[i], i);
    } else {
        rep(i, 1, m) dfs_pre(a[i], i);
    }

    int stp=1;
    ll ans=0, det=0;
    //det 表示树上的答案，ans 表示环上的答案
    memset(dp, 0x3f, sizeof dp);
    dp[1][0][0]=0;
    dp[1][1][0]=2*col[1], dp[1][0][1]=2*(m-col[1]);

    rep(i, 2, n) {
        if(col[i]==col[i-1]) {  //树
            det+=d[i]+d[i-1]-2*d[cal_lca(i-1, i)];
            printf("%lld\n", det+ans);
        } else {    //环
            det+=d[i]+d[i-1];
            ++stp;
            rep(t0, 0, 1) rep(t1, 0, 1) {
                int u=col[i-1], v=col[i];
                const ll z=dp[stp-1][t0][t1];
                if(u==m) {  //如果起点是 m
                    if(!t0 && !t1) continue;    //两条关键边均未经过
                    if(!t1) u=0;    //未经过右侧关键边，则把起点放在左侧。
                }
                if(v==m) {  //如果终点是 m
                    to_min(dp[stp][t0][1], z+m-u);  //走右侧
                    to_min(dp[stp][1][t1], z+u);    //走左侧
                } else {
                    to_min(dp[stp][t0][t1], z+abs(u-v));    //不经过关键点
                    if(u<v && t1 || u>v && t0) {    //经过关键点
                        to_min(dp[stp][1][1], z+m-abs(u-v));
                    }
                }
            }
            if(col[i]^m) rep(t, 0, 1) { //到关键边再回来
                to_min(dp[stp][1][t], dp[stp][0][t]+2*col[i]);
                to_min(dp[stp][t][1], dp[stp][t][0]+2*(m-col[i]));
            }
            printf("%lld\n", det+(ans=min_(min_(dp[stp][0][0], dp[stp][0][1]),
            min_(dp[stp][1][0], dp[stp][1][1]))));
        }
    }
    return 0;
}