AT2663 [ARC079D]Namori Grundy 题解
题面
基环树,树的部分容易发现,每个点的值都是确定的,也就是所有儿子的值的 \(mex\)。直接对非环部分进行树形 dp,考虑环上部分。由于环上的点都还有一条出边,所以如果环上的点通过树形 dp 求得的答案是 \(x\),那么它有两种可能:\(x\) 和所有儿子加入 \(x\) 后的 \(mex\)。随便找一条边断环成链,只需要枚举开头点的两种可能取值,绕一圈还是上述方法全求出其他点的值之后,判断一下这条边是否合法就行了。
点击查看代码
const int N=2e5+13;
struct Edge{int v,nxt;}e[N];
int h[N],tot;
std::vector g[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
int n,d[N],a[N],m,mx1[N],mx2[N],b[N];
bool vis[N];
inline void init(){
std::queue q;while(!q.empty())q.pop();
for(int i=1;i<=n;++i)
if(d[i]==1) vis[i]=1,q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
--d[v];
if(d[v]==1) vis[v]=1,q.push(v);
}
}
}
void dfs1(int u){
vis[u]=1,a[++m]=u;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!vis[v]) dfs1(v);
}
}
void dfs2(int u,int fa){
std::vector son;son.clear();
for(auto v:g[u]){
if(v==fa||vis[v]) continue;
dfs2(v,u);son.pb(mx1[v]);
}
std::sort(son.begin(),son.end());
mx1[u]=0;
for(int i=0,l=son.size();imx1[u]) break;
if(son[i]==mx1[u]) ++mx1[u];
}
mx2[u]=mx1[u]+1;
for(int i=0,l=son.size();imx2[u]) break;
if(son[i]==mx2[u]) ++mx2[u];
}
}
int main(){
//file();
read(n);
for(int i=1;i<=n;++i){
int x;read(x);
d[i]++,d[x]++;
add_edge(i,x),g[x].pb(i);
}
init();
int st=1;while(vis[st]) ++st;
dfs1(st);
memset(vis,0,sizeof vis);
for(int i=1;i<=m;++i) vis[a[i]]=1;
for(int i=1;i<=m;++i) dfs2(a[i],0);
b[a[1]]=mx1[a[1]];
for(int i=2;i<=m;++i){
if(b[a[i-1]]==mx1[a[i]]) b[a[i]]=mx2[a[i]];
else b[a[i]]=mx1[a[i]];
}
if(b[a[1]]!=b[a[m]]) return println("POSSIBLE"),0;
b[a[1]]=mx2[a[1]];
for(int i=2;i<=m;++i){
if(b[a[i-1]]==mx1[a[i]]) b[a[i]]=mx2[a[i]];
else b[a[i]]=mx1[a[i]];
}
if(mx1[a[1]]==b[a[m]]) return println("POSSIBLE"),0;
println("IMPOSSIBLE");
return 0;
}