题目
点这里看题目。
分析
困难的题目。
思路一
从命题逻辑的角度考察一棵树的限制。
某棵树的 /(/operatorname{grow}/) 可以被写作树上结点存在性（在或不在）的合取。考察 /(/operatorname{grow}/) 的并的时候，出于方便运算的考虑可以取补集，于是就变成了析取范式的合取运算。
然而树形结构并没有给析取式带来什么很好的性质，并且两个析取式合并后貌似没法转化成树形，只能作罢。不知道这个思路能不能用在其它题目里面。
思路二
即便我们可以给出最后所有树的 /(/operatorname{grow}/) 对应的一个逻辑条件，我们还是得检查“是否有无穷多组解”，倒不如一开始就从这个切口入手。
考虑 /(m/) 棵树的结点的并集，记为 /(T^/cup/)。可以发现，/(/operatorname{grow}(/mathscr{T})/) 是不完备的，当且仅当存在一棵满足如下条件的树 /(T^*/)：
-
/(T^*/) 包含了 /(T^{/cup}/) 中至少一个叶子。
-
/(T^*/not/in /operatorname{grow}(/mathscr T)/)。
这个条件的充分性是显然的——我们可以随便替换那一个叶子，从而产生无穷棵 /(/not/in /operatorname{grow}(/mathscr T)/) 的树。而必要性应该可以直接通过分析 /(/not/in /operatorname{grow}(/mathscr T)/) 的树的数量是有限的来达成，就不赘述了。反正我也不会
那么，如果我们选定了一个叶子 /(l/)，怎么检查是否有一棵 /(T^*/) 包含了它且不在 /(/operatorname{grow}(/mathscr T)/) 内？最傻瓜的策略是，我们从树根拉一条路径到 /(l/)，但是这当然很容易被一些简单的单链堵住。再做一些调整，我们在其它位置上支出去一些支链——此时就可以发现，支出去的支链必然是叶子，不会更长。如果有另一棵树在支链位置上伸出来了一棵非叶子的子树，那么它不可能防得住我这一个叶子，所以现在我们只需要考虑叶子的限制。
Note.
这里的想法仍然是从“傻瓜策略”出发，一路调整。
思考过程其实更加接近于博弈题目，考虑一些基本的操作，然后看好不好，不好就修修补补，总可以走到一个较优的策略。
最好要熟悉这样的思考方式，不要下一次又想不起来。
那么，我们从 /(/mathscr T/) 中的树的角度来分析。如果有 /(T/in /mathscr T/)，满足 /(T/) 中有一个叶子 /(/overline l/) 是 /(l/) 或者 /(l/) 的祖先，我们考察 /(T/) 上从根到 /(/overline l/) 的路径：如果路径上有一些不是叶子的支链，这样的 /(T/) 不可能产生任何效果，因为我们只会在支链的位置上放或不放叶子；否则，这条路径就可以被描述成 /(01/) 串 /(S_T/)，每个位置描述路径上的结点有没有支出去一个叶子。如果最终我们构造的树上，描述分支情况的 /(01/) 串包含 /(S_T/) 作为一个前缀，那么这样的树就会存在于 /(/operatorname{grow}(T)/) 中，寄了。
对于某个 /(T^/cup/) 上的叶子 /(l/)，找出所有可能的 /(S_T/)，构成集合 /(P_l/)。我们现在需要检查是否存在一个 /(01/) 串，使得任意的 /(P_l/) 中的串都不是它的前缀。显然现在我们应该建立 /(P_l/) 的 Trie 树，且为了方便处理，我们将所有儿子个数不充分的非叶子结点的儿子补全。类似于上面的分析，存在一个上述 /(01/) 串的条件就是，存在一个 Trie 上的叶子，满足它的祖先都不在 /(P_l/) 中。这样的检查可以用标记做到线性。
Note.
两个都是在处理特定“存在性”的检查问题。并且还有一定的共性，那就是考虑一些极小的、特殊的不合法解（当然，也可以是极大的、特殊的合法解）。关键在于，我们要主动施加特殊性质，从而避免繁杂的讨论和太多可能性。
从技术的角度来看，我们可以看作是先有“完整的”/(T^/cup/) 和“完整的”Trie（也就是叶子深度相同，完全补全了），然后再收缩大量无用的结点，精简到了只需要考虑有限的结点的情况。
也可以记忆一下这里的处理方式，
毕竟自己还是走了弯路想错过一次的，不要再犯这样的错误了。
现在我们完成了一个叶子的检查。依据树形结构，我们很容易想到按照 DFS 顺序枚举叶子，这样可以充分利用公共信息。所以，我们首先建立出 /(T^/cup/)，以及 /(/bigcup_l P_l/) 对应的 Trie 树，并把 Trie“补全”。此时我们将每一个 /(T/) 在叶子上的限制挂到 /(T^{/cup}/) 对应的结点上，在 DFS 的时候我们就在这些结点上将限制插入 Trie。处理 Trie 一边的限制也就容易了，我们将 /(P_l/) 处理成树上标记，这样相当于需要处理区间加减、维护全局最小值，线段树即可胜任。最终复杂度即为 /(O(n/log n)/)。
代码
#include <cstdio>
#include <vector>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int MAXN = 4e6 + 5;
template<typename _T>
inline void Read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s ^ '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
inline void Write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) Write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
inline _T Max( const _T &a, const _T &b ) {
return a > b ? a : b;
}
template<typename _T>
inline _T Min( const _T &a, const _T &b ) {
return a < b ? a : b;
}
struct Node {
int ch[2];
Node(): ch{} {}
Node( int L, int R ): ch{ L, R } {}
inline bool IsLeaf() const {
return ! ch[0] && ! ch[1];
}
};
typedef std :: vector<Node> Tree;
int mn[MAXN << 2], tag[MAXN << 2];
int lef[MAXN], rig[MAXN], ID;
std :: vector<int> chg[MAXN];
Tree tre, pref, uni;
int M;
void DFS1( const int &u, int uUni, int uPref ) {
if( tre[u].IsLeaf() ) {
if( uPref )
chg[uUni].push_back( uPref );
return ;
}
rep( k, 0, 1 )
if( int v = tre[u].ch[k] ) {
if( ! uni[uUni].ch[k] ) {
uni.push_back( { 0, 0 } );
uni[uUni].ch[k] = ( int ) uni.size() - 1;
chg[( int ) uni.size() - 1].clear();
}
int nxt = uPref, d;
if( ! tre[u].ch[k ^ 1] ) d = 0;
else {
if( ! tre[tre[u].ch[k ^ 1]].IsLeaf() )
nxt = 0;
else d = 1;
}
if( ! nxt )
DFS1( v, uni[uUni].ch[k], 0 );
else {
if( ! pref[uPref].ch[d] ) {
pref.push_back( { 0, 0 } );
pref[uPref].ch[d] = ( int ) pref.size() - 1;
}
DFS1( v, uni[uUni].ch[k], pref[uPref].ch[d] );
}
}
}
void DFS2( const int &u ) {
if( pref[u].IsLeaf() )
lef[u] = rig[u] = ++ ID;
else {
lef[u] = 1e9, rig[u] = - 1e9;
rep( k, 0, 1 )
if( int v = pref[u].ch[k] ) {
DFS2( v );
lef[u] = Min( lef[u], lef[v] );
rig[u] = Max( rig[u], rig[v] );
}
}
}
inline void Upt( const int &x ) {
mn[x] = Min( mn[x << 1], mn[x << 1 | 1] );
}
inline void Add( const int &x, const int &delt ) {
mn[x] += delt, tag[x] += delt;
}
inline void Normalize( const int &x ) {
if( ! tag[x] ) return ;
Add( x << 1, tag[x] );
Add( x << 1 | 1, tag[x] );
tag[x] = 0;
}
void Build( const int &x, const int &l, const int &r ) {
if( l > r ) return ;
tag[x] = mn[x] = 0;
if( l == r ) return ;
int mid = ( l + r ) >> 1;
Build( x << 1, l, mid );
Build( x << 1 | 1, mid + 1, r );
}
void Update( const int &x, const int &l, const int &r, const int &segL, const int &segR, const int &delt ) {
if( segL <= l && r <= segR ) { Add( x, delt ); return ; }
int mid = ( l + r ) >> 1; Normalize( x );
if( segL <= mid ) Update( x << 1, l, mid, segL, segR, delt );
if( mid < segR ) Update( x << 1 | 1, mid + 1, r, segL, segR, delt );
Upt( x );
}
inline void Init() {
rep( i, 1, ( int ) pref.size() - 1 ) {
if( pref[i].IsLeaf() ) continue;
if( ! pref[i].ch[0] ) {
pref.push_back( Node() );
pref[i].ch[0] = ( int ) pref.size() - 1;
}
if( ! pref[i].ch[1] ) {
pref.push_back( Node() );
pref[i].ch[1] = ( int ) pref.size() - 1;
}
}
ID = 0, DFS2( 1 );
Build( 1, 1, ID );
}
bool DFS4( const int &u ) {
int n = chg[u].size();
rep( i, 0, n - 1 )
Update( 1, 1, ID, lef[chg[u][i]], rig[chg[u][i]], +1 );
if( uni[u].IsLeaf() ) {
if( mn[1] == 0 )
return true;
} else
rep( k, 0, 1 )
if( int v = uni[u].ch[k] )
if( DFS4( v ) ) return true;
rep( i, 0, n - 1 )
Update( 1, 1, ID, lef[chg[u][i]], rig[chg[u][i]], -1 );
return false;
}
int main() {
int T; Read( T );
while( T -- ) {
Read( M );
pref.clear();
pref.push_back( { 0, 0 } );
pref.push_back( { 0, 0 } );
uni.clear();
uni.push_back( { 0, 0 } );
uni.push_back( { 0, 0 } );
chg[0].clear();
chg[1].clear();
bool anyOne = false;
rep( i, 1, M ) {
int n; Read( n );
tre.clear();
tre.push_back( { 0, 0 } );
rep( j, 1, n ) {
int x, y;
Read( x ), Read( y );
tre.push_back( { x, y } );
}
anyOne |= n == 1;
DFS1( 1, 1, 1 );
}
if( anyOne ) {
puts( "Almost Complete" );
continue;
}
Init();
puts( ! DFS4( 1 ) ? "Almost Complete" : "No" );
}
return 0;
}
原创文章，作者：，如若转载，请注明出处：https://blog.ytso.com/278509.html