Rikka with Employees
这题好像有个哥哥叫 [Ynoi2008] stcm 来着，看起来应该比这题的限制更严。
考虑将树拍成 dfn 序，则 \(u\) 对应的子树为 \([\text{dfn}(u),\text{dfn}(u)+\text{size}(u)-1]\)。进行分治，假设分治到 \([l,r]\) 时，标记了 \([1,l-1] \cup [r+1,n]\) 中的所有点，此时我们要处理跨过 \(mid\) 的所有询问。
由于树存在偏序关系，所以跨过 \(mid\) 的询问也存在偏序关系，依次处理即可。
下面是 stcm 的代码：
//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int fa[100010],dfn[100010],rev[100010],siz[100010],tot;
vector<int> G[100010];
void dfs(int u){tot++;dfn[u]=tot;rev[tot]=u;siz[u]=1;for(int i=0;i<G[u].size();i++){int v=G[u][i];dfs(v);siz[u]+=siz[v];}
}
struct Node{int l,r,id;
};
bool operator <(const Node &lhs,const Node &rhs){return lhs.l<rhs.l;
}
void solve(int l,int r,vector<Node> vec){if(vec.empty()){return ;}if(l==r){printf("=%d",vec[0].id);return ;}int l_mid=(l+r)>>1;int r_mid=l_mid+1;vector<Node> l_vec,r_vec,m_vec;for(int i=0;i<vec.size();i++){if(vec[i].r<=l_mid){l_vec.push_back(vec[i]);}else if(vec[i].l>=r_mid){r_vec.push_back(vec[i]);}else{m_vec.push_back(vec[i]);}}sort(m_vec.begin(),m_vec.end());int l_pre=l-1,r_pre=r+1;for(int i=0;i<m_vec.size();i++){int L=m_vec[i].l,R=m_vec[i].r,id=m_vec[i].id;while(l_pre<L-1){l_pre++;printf("+%d",rev[l_pre]);}while(r_pre>R+1){r_pre--;printf("+%d",rev[r_pre]);}printf("=%d",id);}while(l_pre>=l){printf("-");l_pre--;}while(r_pre<=r){printf("-");r_pre++;}while(l_pre<l_mid){l_pre++;printf("+%d",rev[l_pre]);}solve(r_mid,r,r_vec);while(l_pre>=l){printf("-");l_pre--;}while(r_pre>r_mid){r_pre--;printf("+%d",rev[r_pre]);}solve(l,l_mid,l_vec);while(r_pre<=r){printf("-");r_pre++;}
}
int main(){int n;while(~scanf("%d",&n)){tot=0;for(int i=1;i<=n;i++){G[i].clear();}for(int i=2;i<=n;i++){scanf("%d",&fa[i]);G[fa[i]].push_back(i);}dfs(1);vector<Node> vec;for(int i=1;i<=n;i++){vec.push_back((Node){dfn[i],dfn[i]+siz[i]-1,i});}solve(1,n,vec);printf("!\n");}return 0;
}