Description
LOJ3343
判断一个可以叶子可以生长的树的集合是否几乎完备
n
,
m
≤
2
e
6
n,m\le2e6
n,m≤2e6
Solution
一道性质题。考场上的时候想到了一些根据树的形态进行trie上dfs的方式去分治的做法，但是过于复杂，也并没有实现。我并没有意识到一个重要的性质：所有的树都可以由若干种树枝（每一个点的儿子的最小大小不超过1，即一个链在某些节点外挂一个点）生长出来，所以如果只有有限个树枝不能得到，意味着也只有有限个树不能得到。也就是，树枝是一个树的基底，如果几乎所有基底都有，那么也几乎所有树都能表示了。接下来就很简单了。首先只有原本是树枝的树能组成树枝，考虑这些要组成几乎所有树枝，那么就考虑存在一个点没有儿子，或剩下两个儿子的大小为>=1或=1，一共四种情况递归下去都分别几乎完备，那么这个点就是完备的。dfs即可。
O
(
n
)
O(n)
O(n)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 2000005
using namespace std
;
int T
,m
,i
,j
,k
,tot
,n
,t
[maxn
][2],sz
[maxn
],rt
[maxn
],f
[maxn
];
vector
<int> d
[maxn
];
void read(int &x
){
x
=0; char ch
=getchar();
for(;ch
<'0'||ch
>'9';ch
=getchar());
for(;ch
>='0'&&ch
<='9';ch
=getchar()) x
=x
*10+ch
-'0';
}
int getsz(int x
){
sz
[x
]=1,f
[x
]=0;
if (t
[x
][0]) sz
[x
]+=getsz(t
[x
][0]),f
[x
]=max(f
[x
],f
[t
[x
][0]]);
if (t
[x
][1]) sz
[x
]+=getsz(t
[x
][1]),f
[x
]=max(f
[x
],f
[t
[x
][1]]);
f
[x
]=max(f
[x
],min(sz
[t
[x
][0]],sz
[t
[x
][1]]));
return sz
[x
];
}
int check(int k
){
if (!d
[k
].size()) return 0;
for(int i
=0;i
<d
[k
].size();i
++) if (!t
[d
[k
][i
]][0]&&!t
[d
[k
][i
]][1]) return 1;
d
[k
+1].clear();
for(int i
=0;i
<d
[k
].size();i
++) if (t
[d
[k
][i
]][0]&&sz
[t
[d
[k
][i
]][1]]==1)
d
[k
+1].push_back(t
[d
[k
][i
]][0]);
if (!check(k
+1)) return 0;
d
[k
+1].clear();
for(int i
=0;i
<d
[k
].size();i
++) if (t
[d
[k
][i
]][1]&&sz
[t
[d
[k
][i
]][0]]==1)
d
[k
+1].push_back(t
[d
[k
][i
]][1]);
if (!check(k
+1)) return 0;
d
[k
+1].clear();
for(int i
=0;i
<d
[k
].size();i
++) if (t
[d
[k
][i
]][0]&&!t
[d
[k
][i
]][1])
d
[k
+1].push_back(t
[d
[k
][i
]][0]);
if (!check(k
+1)) return 0;
d
[k
+1].clear();
for(int i
=0;i
<d
[k
].size();i
++) if (t
[d
[k
][i
]][1]&&!t
[d
[k
][i
]][0])
d
[k
+1].push_back(t
[d
[k
][i
]][1]);
if (!check(k
+1)) return 0;
return 1;
}
int main(){
freopen("ceshi.in","r",stdin);
read(T
);
while (T
--){
tot
=0,read(m
);
for(i
=1;i
<=m
;i
++){
read(n
),rt
[i
]=tot
+1;
for(j
=1;j
<=n
;j
++) {
read(t
[tot
+j
][0]),read(t
[tot
+j
][1]);
if (t
[tot
+j
][0]) t
[tot
+j
][0]+=tot
;
if (t
[tot
+j
][1]) t
[tot
+j
][1]+=tot
;
} tot
+=n
;
}
for(i
=1;i
<=m
;i
++) getsz(rt
[i
]);
d
[1].clear();
for(i
=1;i
<=m
;i
++) if (f
[rt
[i
]]<=1) d
[1].push_back(rt
[i
]);
if (check(1)) printf("Almost Complete\n");
else printf("No\n");
}
}
