魔力转圈圈

最优解法

对于一次旋转操作，可以通过递归去旋转它的每个儿子。但是显然这么做会超时。注意到对一个结点的操作作用于它的所有子节点，而在它的某个子节点再操作一次这整个子节点为根的子树就可以消除掉之前的一次旋转。所以可以通过给结点打懒标记的方式去控制旋转。最后进行中序遍历的时候如果当前结点被标记过，那么把它的两个儿子也标记起来，并交换两个儿子。
时间复杂度
因为需要懒标记数组，所以空间复杂度

int ch[100005][2];
int lz[100005];
void dfs(int u, vector<int> &ans){
    if(u == 0) return;
    if(lz[u]) {
        lz[ch[u][0]] ^= 1; lz[ch[u][1]] ^= 1; lz[u] = 0;
        swap(ch[u][0], ch[u][1]);
    }
    dfs(ch[u][0], ans); ans.push_back(u); dfs(ch[u][1], ans); return;
}
vector<int> solve(int n, int m, vector<int> l, vector<int> r, vector<int> k){
    assert(l.size() == n && r.size() == n && k.size() == m);
    for(int i = 0; i < n; ++i) ch[i+1][0] = l[i], ch[i+1][1] = r[i];
    memset(lz, 0, sizeof lz);
    for(int i = 0; i < m; ++i) lz[k[i]] ^= 1;
    vector<int> ans; ans.clear();
    dfs(1, ans);
    return ans;
}