[CSP-S2019]树上的数

# upd - 2021.10.14 感谢 @qinyubo 提出的指正，修复了 $n=1$ 的边界的锅。同时~~现代化~~修正了题解的格式，使之更加符合当下的标准。 # 题目 [点这里](https://www.luogu.org/problem/P5659)看题目。 # 分析 这道题真的不简单，细节巨多，恶心死你。但是思路并没有太难。 ### 10pts ~~拿到平均分了！喜闻乐见~~ 写一个暴力全排把它骗过去就可以了。 ### 35pts：暴力+菊花图 两个部分分摆在眼前，先做哪一个呢？ 经验也许告诉你，链的情况比较好做。但是实际上，我强烈推荐写菊花图。 为什么？~~没有为什么~~因为菊花图需要挖掘的性质并不深。 不妨设菊花图的花心为$u$，手玩一下菊花图的数据你会发现，假如将拆边描述为一个点的排列 $p_1,p_2,...,p_{n-1}(\forall1\le i<n ,p_i\not=u)$（也就是说，你按顺序拆掉了 $(u,p_1),(u,p_2),..,(u,p_{n-1})$），那么最后，原来根上的数字 $a_u$ 会去到 $p_1$，原来 $p_1$ 上的数字 $a_{p_1}$ 会去到 $p_2$，原来 $p_2$ 上的数字 $a_{p_2}$ 会去到 $p_3$，...，原来 $p_n$ 上的数字 $a_{p_n}$ 会去到 $u$。如果我们将点按照$(u,p_1,p_2,...,p_n)$的顺序排成一个环的话，整个操作就相当于将每个点上的数字向后移了一位！ 于是很容易地想到一个贪心的构造环的方法。按照 $1,2,3,...,n$ 的顺序，每个数字从自己所在的点选择在环上面的下一个点。这里有两点需要注意： - 在环还没有封闭的时候，请注意它们都还是一些链，所以不要出现两个点的后一个点相同的情况。 - 保证最后会出现一个大环而不是若干个小环，这个可以用并查集维护。 然后恭喜你，你有 35pts 了。~~比平均分高！喜闻乐见~~ ### 60pts：暴力+菊花图+链 下面我们将要攻克单链。 （敲黑板）这个时候就需要挖掘题目的一个非常重要的性质了。假如我们想要把 $a$ 从它的**起始点 $u$** 运到 $b$ 所在的 $v$，并且**就此终止**，那么这个性质可以如下描述： - 对于 $u$，它通向 $v$ 的那一条边一定是 $u$ 所相连的那些边中最先被删除的。不然，$a$ 会被先运走。 - 对于 $a$ 去往 $v$ 的路径上的中转点 $w$，$a$ 离开 $w$ 的那条边一定会紧跟着 $a$ 进入 $w$ 的那条边被删除。不然 $a$ 也会被运走。 - 对于 $v$，$a$ 到达它的那条边一定是 $v$ 所相连的那些边中最后被删除的。不然，$a$ 还是会被运走。 考虑链的情况。由于链上的的点的度最多为 2，所以我们可以直接用一个变量表示两条边的先后关系——左先右后、左后右先或者还未确定。 同样是从小到大枚举数。假如当前枚举到了 $i$，我们当然希望它去到它所能到的最小的那一个点。现在考虑怎么找到这一个点。 最暴力的方法，假如当前 $i$ 在 $u$，我们枚举目标点 $v$。这样我们就可以用 $O(n)$ 的时间扫一遍过去检查可不可行。在单链的情况下，不合法方式只会有一种：经过点的已经要求了的删边顺序和当前需要的删边顺序有冲突。这个可以通过检查变量来实现。 另外，注意链的两个端点需要特殊处理，因为它们的度都是 1，所以就不存在先后关系的说法了。 这样做是 $O(n^3)$。 然后发现这个扩展的方式存在单调性——例如在往左边扩展的时候，我们不能经过 $w$ 这个点，那么在左边并且比 $w$ 离 $u$ 更远的那些点就更不可能走到了。 然后就可以由近及远地枚举点，走不动了就退出，中间选取那些可行的终止点并取出最小的，时间就是 $O(n^2)$。 ### 100pts 终于，我们要直面正解了！ 根据我们从链的情况中得到的结论，我们会发现，对于删边的顺序，不同的点之间是独立的。也就是说对于边 $(u,v)$ 和 $(u,w)$，如果在$u$点上要求 $(u,w)$ 比 $(u,v)$ 先删除，那么这并不影响在 $v$ 点上，$(u,v)$ 与其它边的先后关系。不同点的邻接边删除的顺序不会互相影响。 并且，不会存在这种情况：$(u,v)$ 和 $(u,w)$ 都比 $(u,a)$ 先（后）删除，但是我们却还不知道 $(u,v)$ 和 $(u,w)$ 的先后关系。因为这样的情况会导致错误情况，例如原本应当从 $a$ 运进来，运出去到 $v$ 的数，被中途错误地运到了 $w$。假如对于一个点，我们将它的邻接边抽象成一堆点，用一条有向边 $(u,v)$ 表示边 $u$ 会比 $v$ 先删除，那么合法的方案种**绝对不会存在一个代表一条边的点的出度或入度超过$1$** 。 上面的结论说明，一个点的邻接边抽象成点后，用有向边表示删除先后关系的话，形成的总是一堆链。 当然，根据上面的性质，我们可以知道，在一个点的邻接边中，有一条会强制被第一个删除，有一条会强制被最后一条删除。它们必须是链的起点（第一个）或终点（最后一个）。 于是，假如我们当前枚举一个数$i$，像链一样用一个扩 DFS 展可行的点，记录可以走到的最小的点。对于可走不可走，有三条限制： - 不能有边比当前的第一条边先删除；不能有边比当前的最后一条边后删除 - 一条边不能在存在另一条边紧跟着它被删除的情况下，再出现一条边，也要紧跟着它删除。 - 如果当前的操作会导致当前的第一条边和最后一条边合并在一条链里面，并且除开它们所在的链以外还有一些链没有合并起来，那么这就是不合法的（参考菊花图，这样会导致边删不完） 用 DFS 扩展的时候判一下这些条件。用并查集和一个表示当前有没有入边/出边的数组来维护这些条件。找到了目标点之后就再用一个 DFS 来更新条件。 时间是 $O(n^2)$。 ~~这道题其实赛场满分只有 10 分，那么你其实已经完成了 10 道题了。~~ # 代码 ```cpp #include <cstdio> const int INF = 0x3f3f3f3f; const int MAXN = 2005; template<typename _T> void read( _T &x ) { x = 0; char s = getchar();int f = 1; while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); } while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + s - '0', s = getchar(); } x *= f; } template<typename _T> void write( _T x ) { if( x < 0 ) { putchar( '-' ), x = -x; } if( 9 < x ) { write( x / 10 ); } putchar( x % 10 + '0' ); } template<typename _T> _T MIN( const _T a, const _T b ) { return a < b ? a : b; } struct edge { int to, nxt; }Graph[MAXN << 1]; struct UFS { int fa[MAXN]; bool beg[MAXN], fin[MAXN]; //记录有没有出边或者入边，true 代表没有 void operator () ( const int siz ) { for( int i = 1 ; i <= siz ; i ++ ) fa[i] = i, beg[i] = fin[i] = true; } int& operator [] ( const int u ) { return fa[u] = ( fa[u] == u ? fa[u] : ( *this )[fa[u]] ); } bool operator () ( const int a, const int b ) { return ( *this )[a] == ( *this )[b]; } //并查集维护所属链 }info[MAXN]; int stt[MAXN], fir[MAXN], las[MAXN], deg[MAXN]; int head[MAXN]; int N, cnt; void addEdge( const int from, const int to ) { cnt ++; Graph[cnt].to = to, Graph[cnt].nxt = head[from]; head[from] = cnt, deg[from] ++; } void clear() { cnt = 1; for( int i = 1 ; i <= N ; i ++ ) head[i] = fir[i] = las[i] = 0, info[i]( N - 1 ), deg[i] = 0; } int expand( const int u, const int faE ) { int res = INF; if( faE && ( ! las[u] || las[u] == faE ) ) if( info[u].fin[faE] && ! ( fir[u] && deg[u] > 1 && info[u][faE] == info[u][fir[u]] ) ) res = u; //判断是否可以作为终点 int id, v; for( int i = head[u] ; i ; i = Graph[i].nxt ) { id = i >> 1, v = Graph[i].to; if( id == faE ) continue; if( ! faE ) { if( ! fir[u] || fir[u] == id ) { if( ! info[u].beg[id] ) continue; if( las[u] && deg[u] > 1 && info[u]( id, las[u] ) ) continue; res = MIN( res, expand( v, id ) ); } //起点的移动 } else { if( faE == las[u] || id == fir[u] || info[u]( faE, id ) ) continue; if( ! info[u].beg[id] || ! info[u].fin[faE] ) continue; if( fir[u] && las[u] && deg[u] > 2 && info[u]( fir[u], faE ) && info[u]( id, las[u] ) ) continue; res = MIN( res, expand( v, id ) ); //中转点的移动 } } return res; } bool cover( const int u, const int faE, const int tar ) { if( u == tar ) { las[u] = faE; return true; } int v, id; for( int i = head[u] ; i ; i = Graph[i].nxt ) { v = Graph[i].to, id = i >> 1; if( id ^ faE && cover( v, id, tar ) ) { if( ! faE ) fir[u] = id; else { info[u].fin[faE] = false, info[u].beg[id] = false; info[u][id] = info[u][faE]; deg[u] --; } return true; } } return false; } //更新信息 int main() { int T; read( T ); while( T -- ) { int fr, to; read( N ); clear(); for( int i = 1 ; i <= N ; i ++ ) read( stt[i] ); for( int i = 1 ; i < N ; i ++ ) read( fr ), read( to ), addEdge( fr, to ), addEdge( to, fr ); if( N == 1 ) { puts( "1" ); continue; } for( int i = 1 ; i <= N ; i ++ ) { int mn = expand( stt[i], 0 ); cover( stt[i], 0, mn ); write( mn ), putchar( i == N ? '\n' : ' ' ); } } return 0; }``` ```