Readme

2581.Count-Number-of-Possible-Root-Nodes

既然题目问的是“有多少节点作为根符合要求”，那么我们自然就会思考遍历每个节点作为根的情况。因为节点总数是1e5，所以我们只能用线性的时间遍历完整棵树，并且对于每个根的情况下，用o(1)的时候做出判断。

对于这种题目，有一种常见的套路就是“移根”。假设当前节点A作为根时，答案为a，那么以A的某个邻接节点B未做根时，答案能否快速从a转化而来呢？

假设当前节点A作为根时，它对应的guesses里面有x个顺序的猜想（猜对了），y个逆序的猜想（猜错了）。那么我们转而考虑以B为根时，顺逆序唯一改变的边其实就只有AB之间的路径。所以如果AB边原本是一个顺序的猜想，那么此刻就会变成逆序；如果AB边原本是一个逆序的猜想，那么此刻就会变成顺序。

所以本题的做法就是，先以任意节点（比如说0）为根，一遍dfs计算有多少正确的guess，假设叫做count。然后递归处理它相邻的节点作为根的情况，只需要考察这条相邻边的正逆序变化改变了多少猜想，更新count即可。