美团3-30笔试 第五题

第五题做法
直接对着树做会出错，因为有三角恋的情况（环）
tarjan缩点，强连通分量建边，然后用个set存下来新的root
构造了一颗颗树，树木之间相互独立

int dfs(u){
dp[u][0]=1
dp[u][1]=1
枚举边
dp[u][0]*=dfs(j)
dp[u][0]%=mod

return dp[u][0]+dp[u][1]
}

这个是递归函数
下面要枚举树根，树木之间相互独立，
ans=1
ans*=dfs(root)
ans%=mod

样例的解释好像是要减去一个朋友都不邀请的情况，所以输出ans-1
cout<<ans-1

ac 100%

下面说一下个人看法
我已经退役半年了，很生疏，而且经常笔试迟到半个小时，感觉笔试越来越卷，这个对非竞赛生非常不友好！！！
没必要花大量的时间精力去学这些，性价比太低了，好好准备面试吧！感觉我队友都不一定会写。
错的是这个世界，大家加油吧！